Heaps : Algorithms

Heap

Heap is a kind of data structures based on complete tree principle. By definition, a complete binary search tree of N levels has at least 2^N-1 nodes in it. 
There two properties heap holds :
1. Structural property : This means every level of heap will be completely full except the last level.
Last level will be filled from left to right order.
2. Heap property : It means parent node will be either greater or smaller than its children nodes.

There are two kinds of heaps based on second property:

Max Heap : It maintains the property that every parent node is greater than its children. Root of the max heap is greatest element.

Heap
Max Heap

Min Heap : It maintains the property that every parent node is less than its children. Root of the min heap is least element.

min heap
Min Heap

Usually, heaps are implemented with an array, which eases traversing from child to parent and parent to child; and viewed as tree. Height of a heap with N elements will be O(logN). 

If we want to find child of a parent node i, it would be 2i or 2i+1.

If we want to find parent of a node say i, it would be [i/2].

Given that multiply and divide by 2 can be very efficiently implemented by left and right shifting, these operations are very efficient.

Maximum elements in a heap with height h will be 2^h -1 while minimum number of elements in heap with same height will be 2^(h-1) +1.(One more than nodes with height h-1)

Watch video on heaps : Insertion and deletion in heaps

[youtube=http://www.youtube.com/watch?v=Fx_Bk7-zuxI&w=320&h=266]

Some procedures on heaps

1. Insertion in heap

Insertion in heap happens at the end of heap. Once node is added, heapify property is restored using heapify routines.

Let’s work out an example
Current state of heap is as following, all nodes are satisfying max heap property.

Current Max heap
Now node 10 is added to the heap. We need to check if new node violates max heap property. 
We need to check that parent of currently added node is greater than it. In this case, that does not hold.
So we will swap parent node with current node.
Max heap property violated

After swapping nodes as explained in last step, we should check for if new parent in this case node 14, satisfies heap property. If not, we again swap the largest child and repeat step till we are at root node.. In our case, node 14 satisfies max heap property so we stop there. 

restored heap property

Above mentioned steps are self explanatory and there is no need of algorithm. In above heapify method we are moving down the tree, in insert operation we will move up.

Code

Complexity of this procedure is for O(logN).

2. Deletion in heap

Deletion of node is usually done at root. For deletion of root, replace root node with the last node in heap and then do down shift. As new node replacing root may violate heap property, we need to check with its children. In Max heap, check if new node is greater than both its children. If not then swap it with largest child and then again repeat it till node replacing root finds its valid place.

Algorithm (This is for max heapify)
  1. Let i be the index which we doubt that might violate heap property.
  2. left = 2i, right = 2i+1, largest = a[i]
  3. Check if left child is with in array limits, if yes, check if it is greater than the a[i].
  4. If left is greater than a[i], then largest till now is left, largest <– left.
  5. Check if right is with in array limit, if yes, check if it is greater than largest, then change the largest, largest <– right.
  6. Swap largest and a[i].
  7. Now, repeat step 1 to 6 with largest, till we see an element which does not violate heap property.

 Let’s take an example:

Current heap


Now let’s say we delete node 14. 

First step is to replace it with last node. In this case 6 will replace 14.

Last node replacing root

Node 6 violates max heap property. So, find the largest child of 6, node 12 in this case.Swap node 6 and node 12.

Heap after swapping

Again repeat step with node 6 and node 7. Final heap will be like

Final heap

Code

3. Building a heap from a given array of elements.

This operation can easily be done using heapify methods explained above. 

Algorithm

  1. Start from the middle element of the array, let’s say i
  2. Heapify with given index.
  3. Decrease index by one. Repeat step 2 till we reach first element.

Code

Complexity of this procedure is O(N).How this complexity becomes O(N) while for adding each node will need log N time to heapify and if there are N nodes, it should be O(N log N).
Idea here that nodes at the lower most level do not move at all. Nodes at one level above lower most, move at most by one level and so on.
If height of heap is h, number of node will be 2^h. So 2^h/2 = 2^h-1 nodes never move.
2^h-2 nodes move by one level and so on.

4. Heapsort

Heap sort combines property of both insertion sort (no extra space required) and merge sort (time complexity being O(NlogN)). 
It can be easily achieved by using above two procedures.

Algorithm

  1. Build MAX heap from the given array.
  2. Swap first and last element of the array. Last element is now at its proper position.
  3. Decrease the effective size of heap to be heapify.
  4. Heapify with first element of the array.
  5. Repeat step 2 , 3 and 4 till we reach the second element of the array.

Code

Complexity of above procedure is O(NlogN).