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

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.

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