How can I create Min stl priority_queue?

Question

The default stl priority queue is a Max one (Top function returns the largest element).

Say, for simplicity, that it is a priority queue of int values.

Solution 1

Use std::greater as the comparison function:

std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

Solution 2

One way would be to define a suitable comparator with which to operate on the ordinary priority queue, such that its priority gets reversed:

 #include <iostream>  
 #include <queue>  
 using namespace std;  

 struct compare  
 {  
   bool operator()(const int& l, const int& r)  
   {  
       return l > r;  
   }  
 };  

 int main()  
 {  
     priority_queue<int,vector<int>, compare > pq;  

     pq.push(3);  
     pq.push(5);  
     pq.push(1);  
     pq.push(8);  
     while ( !pq.empty() )  
     {  
         cout << pq.top() << endl;  
         pq.pop();  
     }  
     cin.get();  
 }

Which would output 1, 3, 5, 8 respectively.

Some examples of using priority queues via STL and Sedgewick's implementations are given here.

Solution 3

The third template parameter for priority_queue is the comparator. Set it to use greater.

e.g.

std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;

You'll need #include <functional> for std::greater.

Solution 4

You can do it in multiple ways:
1. Using greater as comparison function :

 #include <bits/stdc++.h>

using namespace std;

int main()
{
    priority_queue<int,vector<int>,greater<int> >pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);

    while(!pq.empty())
    {
        int r = pq.top();
        pq.pop();
        cout<<r<< " ";
    }
    return 0;
}

2. Inserting values by changing their sign (using minus (-) for positive number and using plus (+) for negative number :

int main()
{
    priority_queue<int>pq2;
    pq2.push(-1); //for +1
    pq2.push(-2); //for +2
    pq2.push(-3); //for +3
    pq2.push(4);  //for -4

    while(!pq2.empty())
    {
        int r = pq2.top();
        pq2.pop();
        cout<<-r<<" ";
    }

    return 0;
}

3. Using custom structure or class :

struct compare
{
    bool operator()(const int & a, const int & b)
    {
        return a>b;
    }
};

int main()
{

    priority_queue<int,vector<int>,compare> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);

    while(!pq.empty())
    {
        int r = pq.top();
        pq.pop();
        cout<<r<<" ";
    }

    return 0;
}

4. Using custom structure or class you can use priority_queue in any order. Suppose, we want to sort people in descending order according to their salary and if tie then according to their age.

    struct people
    {
        int age,salary;

    };
    struct compare{
    bool operator()(const people & a, const people & b)
        {
            if(a.salary==b.salary)
            {
                return a.age>b.age;
            }
            else
            {
                return a.salary>b.salary;
            }

    }
    };
    int main()
    {

        priority_queue<people,vector<people>,compare> pq;
        people person1,person2,person3;
        person1.salary=100;
        person1.age = 50;
        person2.salary=80;
        person2.age = 40;
        person3.salary = 100;
        person3.age=40;


        pq.push(person1);
        pq.push(person2);
        pq.push(person3);

        while(!pq.empty())
        {
            people r = pq.top();
            pq.pop();
            cout<<r.salary<<" "<<r.age<<endl;
    }

5. Same result can be obtained by operator overloading :

   struct people
   {
   int age,salary;
   
   bool operator< (const people & p)const
   {
       if(salary==p.salary)
       {
           return age>p.age;
       }
       else
       {
           return salary>p.salary;
       }
   }};
   

   In main function :

   priority_queue<people> pq;
   people person1,person2,person3;
   person1.salary=100;
   person1.age = 50;
   person2.salary=80;
   person2.age = 40;
   person3.salary = 100;
   person3.age=40;
   
   
   pq.push(person1);
   pq.push(person2);
   pq.push(person3);
   
   while(!pq.empty())
   {
       people r = pq.top();
       pq.pop();
       cout<<r.salary<<" "<<r.age<<endl;
   }
   

Solution 5

In C++11 you could also create an alias for convenience:

template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;

And use it like this:

min_heap<int> my_heap;

View more solutions

Comments

[amitlicht]

and if it is not priority queue of ints, but some MyClass object?

[Khaled Alshaya]

@eriks You have some options. Either your class defines operator>, which would work like charm with std::greater. You could write your own functor also instead of std::greater if you like.

[Peter Alexander]

@AraK, I think you mean operator< ;)

[Khaled Alshaya]

@Poita_ Doesn't std::greater use operator> and std::less use operator<? Sorry if I am missing something.

[James McNellis]

@AraK, @Poita_: Yes, std::greater uses operator>. @eriks: What AraK said above is the correct way to do this for user-defined types.

[Shvalb]

The default comparison functor is less<T>, so logically, to reverse the order, you would use greater<T>.

[Moha the almighty camel]

@Potatoswatter: that is not always the case.

[Dhruv Mullick]

Can you please explain why we use l>r and not l<r, for implementing a min priority queue?

[Diaa]

The default comparator for the priority queue is l<r. You can see that in the constructor default parameter. By doing l>r or r<l you'd get the opposite.

[piyukr]

@JamesMcNellis Would it be incorrect to write greater<int>() in place of greater<int> ? Can you please tell me the difference between the two?

[reggaeguitar]

This is better than the accepted answer because it also mentions to #include <functional>

[Admin]

Why do we have to add vector <int> ?? wouldn't it be obvious, as we already said we want int? What other options are there for the second parameter?

[Tanmay Garg]

@CarryonSmiling in the standard template library, the vector and deque classes fulfill the requirements that an underlying container must meet for a priority_queue. You can also use a custom container class. You can find a much elaborate explanation on cplusplus.com/reference/queue/priority_queue

[Rockstar5645]

Don't you mean bool operator > (const people & p)const in 5) operator overloading

[Rockstar5645]

Actually, your right, 5) does work, it's just weird, I've never seen < overloaded like that, it's better to overload > and use greater<people>

[Telenoobies]

Can someone explain why does min heap uses greater<int> not less<int> ?

[AER]

@AndyUK Hello, ¿why you use a struct for implement the comparation operator? thanks in advance

[qwr]

The default priority queue in C++ is a max priority queue.

[Leonid Vasilev]

@Telenoobies relevant quote from C++ reference: "Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare."

[Escape0707]

Since C++ 14, you can use std::greater<> instead. This will default to std::greater<void> and deduce the actual compared type for you.

[Saurabh Rana]

@DhruvMullick as qwr said, by default the PQ is max priority queue and the comparator used is less<> so in order to get the min PQ you need to reverse that by using greater<> or l>r.

[Marlon]

@DhruvMullick It's a little confusing but think of the compare function to return true when you want to put the element at the bottom of the priority queue, and false to put the element at the top of the priority queue. Since default implementation is std::less, that will put the smallest element at the bottom of the priority queue and therefore the largest element is at the top (max heap). To create a min heap we use std::greater which puts the largest element at the bottom and smallest element at the top (min heap).

[Marlon]

@Telenoobies It's a little confusing but think of the compare function to return true when you want to put the element at the bottom of the priority queue, and false to put the element at the top of the priority queue. Since default implementation is std::less, that will put the smallest element at the bottom of the priority queue and therefore the largest element is at the top (max heap). To create a min heap we use std::greater which puts the largest element at the bottom and smallest element at the top (min heap).

[afterxleep]

@AER It is common to use structs for functors that will be passed to STL algorithms. You could use a class as well if you want, it doesn't matter too much. The significant difference is that, structs by default have all its member as “public”, and class by default have all its member “private”.