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
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).
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 2i at 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=2h and 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.
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.