Facebook

Implementation and Merging of Heaps

Implementation

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).

 

Fig 1 : Heap

 

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 :

  • A new heap is created with root node storing k and two given heaps as subtrees.
  • Perform downheap to restore  relational property of heap.

Example

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

Fig 3 : h1 and h2

 

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

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

 

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

Fig 5 : Downheap operation
Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar