1. Introduction of Heap
-
Definition
- Heap is a complete binary tree that satisfies the heap properties (min or max heap).
- Max Heap: Every node has greater or equal key(value) to their children.
- Min Heap: Every node has smaller or equal key(value) to their children.
-
Properties
- Basically heap is an array.
- Height of any heap will be
log(n)
only. - Left child is at
2*i
- Right child is at
2*i+1
- Parent is at
i/2
2. Insertion (max heap)
1) Insert the element to the end of the array.
2) Then swap the element with its parent until the parent is greater or equal to the element
void Insert(int arr[], int i){
while(i > 0 && arr[i/2] < arr[i]){
// Swapping parent and current
swap(arr[i/2], arr[i]);
// Move on to the next element
i = i/2;
}
}
3. Deletion (max heap)
In heap, deletion means deleting the root node.
1) Swap the element with the given index with the last element in the heap.
2) Delete the current last element.
3) Compare swapped element's children. Swap the element with the greater child (only when any of the children are greater or equal to the element).
4) Repeat the process until we find the place where both children are smaller than the element.
void deleteRoot(int arr[], int& n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with last element
arr[0] = lastElement;
// Decrease size of heap by 1 (element deleted)
n = n - 1;
// Start from the bottom
int i = n;
// Construct the heap again after the deletion
while(true){
// After we proceed the root node, break out of the loop.
if(i < 0)break;
// Compare two children and swap
if(i*2 <= n && arr[i] < arr[i*2]){
swap(arr[i], arr[i*2]);
} else if(arr[i] < arr[i*2+1]){
swap(arr[i], arr[i*2+1]);
}
i--;
}
}
4. Heap Sort
Use one of properties of deletion.
Every time we delete an element from the heap, we get an additional empty space at the end of the array.
We also get the maximum element among the heap.
Therefore, if we keep inserting those deleted elements to the end of the array, the array will be eventually sorted.
5. Heapify
Heapify allows you to create a heap within O(N) time complexity. Using insertion method would take O(N*log(N)).
-
Heapify starts from the bottom. It repeatedly compares every children of nodes and swap with the parent until it reaches to the root node.
- Max heap example:
swap(arr[i], max(arr[2*i], arr[2*i+1]))
- Min heap example:
swap(arr[i], min(arr[2*i], arr[2*i+1]))
- Max heap example:
6. How to use Heap in C++
-
priority_queue<T>
can be used as Max Heap in C++. Max Heap is the default behavior of the library.- ex)
priority_queue<T> pq;
- ex)
-
priority_queue<T>
can be used as Min Heap in C++. You just need to pass some additional arguments to the constructor.- ex)
priority_queue <T, vector<T>, greater<T> > pq;
- ex)
Top comments (0)