Question

Recall that an array could be a convenient way of storing the elements of a Heap. Give a Pseudocode that determines whether an array H[1..N] is indeed a Heap, i.e., it’s elements satisfy the Heap property.

Answer 1

Array:

• Array is the part of any programming language like c,c++,python etc.
• It is define as"collection of similar data types elements".Which means it contain only one type as datatypes in which is declared. Like: int A[ ] (all elemnts are int type), char B[ ] , etc.
• In array each element are identified by array index.Where is is denoted by A[1],A[1]......................A[n]
• Array is stored in a way that the position of each element can be computed from its index value by a mathematical formula.
• Formula: Address of A [ I ] = B + W * ( I – LB )​

  B = Base address
  W = Storage Size of one element stored in the array (in byte)
  I = Subscript of element whose address is to be found  

  LB = Lower limit / Lower Bound of subscript, if not specified assume 0 (zero)​​​​

• Array are used to hold one value at a time.
• Array Representation:

Int A[6]={33,32,31,43,35,85}

1001   1004 1008 1012 1016 1020

33

32

31

43

35

85

A[0] A[1] A[2] A[3] A[4] A[5]

Where:1001 ,1004......................1020 = address or memory allocatrion

33,32......................85= Elemets of array

A[0] ,A[1]...................A[5] = Index value

Heap:

• Tree structure is known as Heap.
• A heap is a binary tree with keys at its nodes.
• In heap the value of each node is less than or equal to the value of parent node.
• In Heap the root of the binary tree(first elements) is the largest value or minimum value also it is knowm as max haep and min heap.
• The parent at each node is ≥ at its children node.

An array could be a convenient way of storing the elements of a Heap in following way:

1. Sequance representation of heap:

• Sequance representation of heap is same as like array representation.
• In sequence reprentation ,If the root of any sub-tree at the position n , then it left most child will be at position ( 2n+1) , And right most child at (2n+2) and after that the parent node at the position (n-1)/2 where n≠0.

• Sequance representation of heap:

1001 1004 1008 1012 1016 1020

33

32

31

43

35

85

A[0] A[1] A[2] A[3] A[4] A[5]

Where:1001 ,1004......................1020 = address or memory allocatrion.

33,32......................85= Elemets of array.

A[0] ,A[1]...................A[5] = Index value.

2. Array representation of Heap's:

• Store heap’s elements in an array (whose elements indexed, for convenience, 1 to n) in top-down left-to-right order.
• Example:

Properties of a Heap:

• Heap’s elements are ordered top down, but they are not ordered left to right.
• The root contains the largest value.
• The subtree rooted at any node of a heap is also a heap.
• A heap can be represented as an array.

Pseudocode that determines whether an array H[1..N] is indeed a Heap:

Here: H[1...n]= array which elemnts tends to 1 to n.

N=represent the number of elments in array H[1....n]

1. k=2 to N (repeat 2 to 9) /* k= index value of array H[1....n] */
2. n=k and T=H[k] /* T= temporary variabl */
3. Root node = n/2 (repeat 5 to 8) /* n position of root node*/
4. while (i > 1) AND (T >H [root] )
5. H [ i ] = H [root]
6. i = root , root=n/2 /* next root node*/  
7. root > 1 then:
8. root = 1 End step 4.
9. H [ i ]= T End step 1. /* copy new element value*/
10. Return.