Implementation and Merging of Heaps


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.


Screen Shot 2014-05-21 at 2.56.59 PM

Fig 1 : Heap


Screen Shot 2014-05-21 at 4.28.59 PM

Fig 2 : Implementation of Heap


Merging two heaps

If two heaps are to be merged and a key(k) has to be inserted then we follow these steps :


Given are the two heaps h1 and h2 in Fig 3.We need to merge them and add 5 to it.

Screen Shot 2014-05-21 at 4.03.25 PM

Fig 3 : h1 and h2


A new heap h3  is created with root node storing 5 and h1,h2 as subtrees(Fig 4).

Screen Shot 2014-05-21 at 4.09.04 PM

Fig 4 : Merging of h1 and h2 with insertion of key 5.


Perform downheap operation to restore heap property(Fig 5).

Screen Shot 2014-05-21 at 4.11.38 PM

Fig 5 : Downheap operation

Short URL:
Author: Cusp2207 on May 22, 2014
Category: Computer Science, Data Structures

Leave a Reply

Last articles