I have discussed the priority queue and implementations of queue, vector. Now, we are gonna discuss about min heap, also known as a priority queue. So, what’s this data structure? It has 4 main methods:
size()
- returns the number of the elementsfront()
- return the current minimum elementpop()
- deletes the current minimum elementpush(element)
- insert new element to the heap
How do we implement this? Of course, we could use array and track the minimum element. However, if we need to delete, we have to find the next minimum element, which is too costly. In heap, pop()
is done in O(logN) time, and the front()
is done in O(1) time.
Idea
We can’t just use array and find the minimum element, then delete it, and find the next minimum element, as this operation takes O(N) time. We could use sorted array and add elements to it using binary search, but doesn’t solve our problems either because of the shifting the array.
I have written about graph. And now we’re gonna talk about trees. Tree is a graph that does not contain any cycles. Cycle is a a non-empty trail in which only the first and last vertices are equal. So, how are we gonna use this? Btw, we are talking about rooted tree.
Let’s create a rooted tree with some rule. The rule is simple
- Pick any node, and every child of this node’s value is greater than the current node’s value.
- Every node has at most two children (we call this a binary tree).
With these two rules, our insert and delete can be easy The idea is simple, but is it efficient? Yes, if we can keep the tree balanced, our height of the tree is at most log(N)
, so adding or deleting node is done in O(log(N)). Here is an example tree:
![Image](./images/min_heap.drawio.png)
How do we track and store the children and parent? We use a simple array. The ith
element’s left child is the (i*2 + 1)th
element, and the right child is the (i*2 + 2)th
element. Our root index is 0. Here’s an example:
![Image](./images/min_heap_indexing.drawio.png)
Insertion
To insert a new node into the min-heap, we follow these steps:
- Add the Node: Insert the new node at the end of the heap (i.e., the next available leaf position).
- Heapify Up: Compare the newly added node with its parent node. If the new node is smaller, swap it with its parent. Repeat this process until the new node is in the correct position or it becomes the root. This ensures the tree remains balanced and maintains the min-heap property.
For example, let’s add 2 into the heap
![Image](./images/min_heap_add.drawio.png)
Deletion
To delete the root node (which is the minimum element in a min-heap), we follow these steps:
- Swap with Last Node: Replace the root node with the last node in the heap (i.e., the most recently added leaf node).
- Remove Last Node: Remove the last node (which was swapped to the root).
- Heapify Down: Compare the new root with its children. If the new root is larger than either of its children, swap it with the smaller child. Repeat this process until the new root is in the correct position or it becomes a leaf node.
![Image](./images/min_heap_delete.drawio.png)
Implementation
Laet’s dive into the code. We’ll declare our structure. We need the size and the elements of the heap, so we will use a vector.
class MinHeap {
private:
vector<int> a; // store the heap values
int s; // size
}
now lets add some elements
void push(int x) {
a.push_back(x); // add this to the last
int index = s; // last index
s++; // // update the size
while(index && a[parent(index)] > a[index]) { // / if it's smaller than the parent we will need to swap
swap(a[index], a[parent(index)]); // swap
index = parent(index); // update the current index
}
}
Now for removal
void pop() {
if(s == 0) return;
a[0] = a[s-1]; // set the root as the last element
a.pop_back(); // remove last element
s--; // update the size
int index = 0;
while(left_child(index) < s) {
// find minimum node of the childrens
int min_index = left_child(index);
if(right_child(index) < s && a[min_index] > a[right_child(index)]) {
min_index = right_child(index);
}
if(a[min_index] >= a[index]) break; // if our current node is smaller than the both nodes, we dont have to nothing
swap(a[index], a[min_index]); // swap the minimum
index = min_index; // keep going
}
}
Conclusion
We have explored the concept and implementation of the min-heap, a fundamental data structure used in various applications such as priority queues and graph algorithms. We used just vector but the underlying idea is what makes it working.
The key aspects of a min-heap are maintaining a balanced tree structure and adhering to the heap property. The rules governing min-heaps make it straightforward to locate and reorder elements efficiently. Balancing the tree ensures that operations like insertion and deletion remain efficient, maintaining logarithmic time complexity.
Understanding these principles is essential for effectively leveraging min-heaps in real-world applications.