Implementation and Merging of Heaps

http://install4install.com

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.

 

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 :

Example

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: http://tinyit.cc/eff0
Author: Cusp2207 on May 22, 2014
Category: Computer Science, Data Structures
Tags:

Leave a Reply

Last articles