Heaps of n keys can be represented by array of length n+1(Fig 2).For a node at rank i ,the left child is at rank 2i +1 and the right child is at rank 2i +2.The links between nodes are not stored explicitly.
- In Fig 1,heap has 7 keys i.e n =7.
- Array will be of length 8(n+1=7+1).
Merging two heaps
If two heaps are to be merged and a key(k) has to be inserted then we follow these steps :
- A new heap is created with root node storing k and two given heaps as subtrees.
- Perform downheap to restore relational property of heap.
Given are the two heaps h1 and h2 in Fig 3.We need to merge them and add 5 to it.
A new heap h3 is created with root node storing 5 and h1,h2 as subtrees(Fig 4).
Perform downheap operation to restore heap property(Fig 5).