Heaps : Algorithms

Heaps

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. Heap is nearly complete tree. Heap maintains a property called as heap property which holds across all nodes of the heap. 
There are two kinds of heaps we frequently deal with :

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

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

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)

Some procedures on heaps

1. Heapify - This procedure can be again sub-classified as MAX-heapify or MIN-heapify 

This procedure maintains the heap property of the heap. Every time we add or delete any element from heap, we just run this procedure and adjust other elements to maintain heap property.
Heapify is always called with an element index where we can be safely assume that all elements below it maintain heap property.

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.

We will code it. :)

Example :

Step 1  : i =2;

Max heap property violation

Step 2 : 

Compare left child and parent

Step 3 and 4:

Compare right child and parent

Step 5 :

Swap largest and parent

Complexity of this procedure is for O(logN).

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

Complexity of this procedure is O(N).

3. Heap-sort

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.

Complexity of above procedure is O(NlogN).

In next post we would code all above algorithms and discuss min heaps which are used as priority queues.

Reference : http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844