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.
If we want to find child of a parent node i, it would be 2i or 2i+1.
Watch video on heaps : Insertion and deletion in heaps
Some procedures on heaps
1. Insertion in heap
|Current Max heap|
|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|
2. Deletion in heap
Algorithm (This is for max heapify)
- Let i be the index which we doubt that might violate heap property.
- left = 2i, right = 2i+1, largest = a[i]
- Check if left child is with in array limits, if yes, check if it is greater than the a[i].
- If left is greater than a[i], then largest till now is left, largest <– left.
- Check if right is with in array limit, if yes, check if it is greater than largest, then change the largest, largest <– right.
- Swap largest and a[i].
- Now, repeat step 1 to 6 with largest, till we see an element which does not violate heap property.
Let’s take an example:
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
3. Building a heap from a given array of elements.
- Start from the middle element of the array, let’s say i
- Heapify with given index.
- Decrease index by one. Repeat step 2 till we reach first element.
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.
- Build MAX heap from the given array.
- Swap first and last element of the array. Last element is now at its proper position.
- Decrease the effective size of heap to be heapify.
- Heapify with first element of the array.
- Repeat step 2 , 3 and 4 till we reach the second element of the array.
Complexity of above procedure is O(NlogN).