Comparators in priority_queue in cpp

help
1

Can anyone please help me, i have this doubt since a long time and i didn’t find anything helpful on internet?

Can anyone please explain how comparators(or operators) work with priority_queues?
For creating min heap, we use following struct compare
struct compare{
bool operator()(item a, item b){
return a > b;
}
};

The C++ reference has this description of compare :
A binary predicate that takes two elements (of type T) as arguments and returns a bool .
The expression comp(a,b) , where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.
The priority_queue uses this function to maintain the elements sorted in a way that preserves heap properties (i.e., that the element popped is the last according to this strict weak ordering ).
This can be a function pointer or a function object, and defaults to less<T> , which returns the same as applying the less-than operator (a<b ).

Now as per this our operator returns true when a > b and that will mean that a will go before b in our priority queue. So doesn’t our priority queue became max heap(since a>b) instead of min heap?
But it works like a min heap, i don’t know where am i wrong?

Thanks in advance.
@cubefreak777 @vijju123 @ssrivastava990

2

You can look it up from here.

3 
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

Yes, i’ve read it.
But my question is how
bool operator()(int a, int b){ return a>b; }
results in min heap instead of max heap.

If operator returns true, then it will place a before b in the sequence,right??And that should result in a max heap.

5

it is min heap , the priority goes to second element “b”

6

Just posting this for anyone in the future. The cppreference on priority queue gives the following information

" Compare - A [Compare] type providing a strict weak ordering.
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]."

1 Like