Heaps

http://install4install.com

A Heap is a Binary tree(Refer http://letslearncs.com/binary-trees/) that stores keys at it’s internal nodes and satisfies two additional properties which are :

Relational Property

It follows either  Min-Heap or Max-Heap property.The  Max-Heap property says that  keys of each and every child  will be less than the key   of parent(Fig 2)whereas Min-Heap  property says that  keys of each and every child are either greater than or equal to the key of parent(Fig 1).

 

Screen Shot 2014-05-19 at 4.03.28 PM

Fig 1 : Maxheap

Screen Shot 2014-05-19 at 4.01.04 PM

Fig 2 : Minhea

 

Structural Property

All the levels are full except the last level which is left justified.Left justified means that the parents of terminal nodes will have left child and may/may not have right child(Fig 4).Tree in Fig 3 fails to satisfy structural property.

Screen Shot 2014-05-19 at 4.57.01 PM

Fig 3 : Incomplete Binary Tree

Screen Shot 2014-05-19 at 4.52.55 PM

Fig 4 : Left Filled Binary Tree

Height of a Heap

The height of heap is O(log n).

Insertion in Heap

The insertion in Heap follows three steps :

 

Example

Screen Shot 2014-05-20 at 5.15.10 PM

 

 

 

 

 

 

 

 

Screen Shot 2014-05-20 at 5.18.37 PM

Fig 5 : Insert 5 at terminal node

Screen Shot 2014-05-20 at 5.23.08 PM

Fig 6: Use upheap method

 

Screen Shot 2014-05-20 at 5.26.39 PM

Fig 7 : Use upheap again

 

Removal from a Heap

Example

Screen Shot 2014-05-20 at 5.38.48 PM

Fig 8 : Remove Min element

Screen Shot 2014-05-20 at 5.44.56 PM

Fig 9 : Remove min element

Screen Shot 2014-05-20 at 5.46.55 PM

Fig 9 : Move 26 to root

 

 

 

 

 

 

 

 

 

 

Screen Shot 2014-05-20 at 5.49.05 PM

Fig 10 : Use downheap method

 

Screen Shot 2014-05-20 at 5.50.22 PM

Fig 11 : Use downheap

Screen Shot 2014-05-20 at 5.52.00 PM

Fig 11 : Use downheap



Short URL: http://tinyit.cc/c9d404
Author: Cusp2207 on May 21, 2014
Category: Computer Science
Tags:

Leave a Reply

Last articles