# 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

Rate this post