Facebook

Heaps

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
  • Structural Property

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

  • Let h be the height of heap with n keys.
  • The maximum no. of keys in heap  can be 2n.
  • Since there 2at depth i =0,1,2,3,....h-1 and at least one key at depth h,we have   1 +2 +4 + 2h-1 +1.
  • Thus n=2and height= O( log n).
  • h=O(log n).

Insertion in Heap

The insertion in Heap follows three steps :

  • Find the node(Say n) where key(k) has to be inserted.
  • Store key(k) at node(n).
  • After the insertion of new key,heap property can get violated.
  • Use Upheap technique to restore heap property.
  • The upheap technique swaps the key along with the upward path from the insertion node.
  • This method is followed until the key(k) reaches a node whose parent has a smaller/equal value to k.

 

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

  • This method removes the root i.e the minimum value from the heap.
  • The root is deleted and the last key takes the place at root node
  • Downheap technique is followed till the heap property is restored.
  • Downheap swaps key along the downward path.
  • Terminate downheap method leaf/terminal level is reached and key of parent is less than key of child.

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