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 elements
  • front() - return the current minimum element
  • pop() - deletes the current minimum element
  • push(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

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

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

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

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.