How to implement min-heap using C++ STL?

A min-heap is a binary tree such that:
1. The data contained in each node is less than (or equal to) the data in that node’s children.
2. The binary tree is complete

The C++ Standard Library consists of a container named priority_queue. A priority queue is technically a max-heap but it can be used to implement a min-heap by tweaking its constructor.

priority_queue<data_type,container_object,comparison>

The parameter comparison is used to order the heap. It may be a function pointer or function object capable of comparisons and must have two arguments.
The container object is by default a vector.

Example to implement a min-heap:

#include <queue>
#include <iostream>

using namespace std;


struct comparator
{
    bool operator()(int a, int b)
    {
        return a > b;
    }
};


int main()
{
    priority_queue<int, vector<int>, comparator> minHeap;
    minHeap.push(12);
    minHeap.push(8);
    minHeap.push(15);
    minHeap.push(2);
    minHeap.push(3);
    minHeap.push(9);

    while (!minHeap.empty())
    {
        cout<<minHeap.top()<<" ";
        minHeap.pop();
    }

    return 0;
}

Output:

2  3  8  9  12  15

Note:
Instead of defining an explicit comparator structure, one can also use greater<data_type>. This is defined in the functional package.
Example:

#include <queue>
#include <iostream>

using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int> > minHeap;
    minHeap.push(12);
    minHeap.push(8);
    minHeap.push(15);
    minHeap.push(2);

    while (!minHeap.empty())
    {
        cout<<minHeap.top()<<" ";
        minHeap.pop();
    }

    return 0;
}

Output:

2  8  12  15

This article is written by

Please comment below, if you have any doubts or find any error in the above article.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top