Heap : Suppose 'H' is a complete binary tree with 'n' elements. Then 'H' is called a Heap, as a 'maxheap', if each node 'N' of 'H' has the following property:
The value at 'N' is greater than or equal to the value at each of the children of N. Accordingly, the value at N is greater than or equal to the value at any of the descerdants of N.
Algorithm to insert an element in to the heap: Consider a heap 'H' with 'N' elements is stored in the array TREE and an ITEM of information is given. This procedure inserts 'ITEM' as a new element of 'H'.'PTR' gives the location of ITEM as it rises in the tree, and 'PAR' denotes the location of the parent of 'ITEM'.
1. [ Add new node to 'H' and initialize PTR ] set N=N+1 and PTR=N
2. [ Find location to insert ITEM ]
Repeat steps 3 to 6 while PTR>1
3. set PAR= [PTR/2] (floor operation)
[Location of parent node] If ITEM<= TREE
[PAR] then step 4 else go to step 5.
4. set TREE
[PTR]=ITEM and
return End of If
structure
5. set TREE [PTR]= TREE [PAR] [moves node down]
6 set PTR
=PAR//» updates
PTR
//» End of
step2 loop
7. //» Comments Assign
ITEM as the root of H] set
TREE [1] = ITEM
8. Return
10. (b) Construction of heap :
Step 1 inserting 44
Step 2 Inserting 30
Step 3 Inserting 50
Step 4 inserting 22
Step 5 inserting 60
step 6 inserting 50
This is the required heap.
