For an array, if we want to sort in descending order, we can use the greater() comparator. What it means is that the greater element should come before smaller element. But, in case of priority_queue in C++, if we use greater() as comparator, it makes the top element the smallest. So, if I write something like following:-
while(!pq.empty()) // pq is priority_queue of integers
{
auto c = pq.top();
pq.pop();
cout << c << " ";
}
Above code results in integers being printed in ascending order. Can someone explain why is that so? Or does comparator have different meaning in case of priority_queue? For a fact, I know that by default, the priority queue in C++ is max_heap. Does this have to do anything with it? I searched on internet but couldn't find valid reason for this. Thanks.
By default, the comparator is
less<T>(where T is the type, 'int' in this case). This means that the .top() of the priority queue will be the largest element.But if you change this and use
greater<T>, it will be reversed. Using:std::priority_queue< int, std::vector<int>, std::greater<int> > pq;Then
pq.top()will be the smallest element.I think this is because the comparator given to the priority queue is the one it uses it as the < operator. Therefore, if you give it the greater than operator as the less than operator, then when it finds the 'largest' element in its opinion, it will actually find the smallest element.
This link gives information about the priority_queue constructor.
Thanks for the explanation, that makes sense. But still leaves some gaps. My opinion: The comparator is less by default. So, order elements in heap such that the less priority elements appear at top. That's why the greatest element is at top because it has least priority. Then, when we say greater, we want highest priority element at top, hence the smallest element is at top because of highest priority. I just feel its easier with this intuition. What say?
I remind it as: priority_queue.top() works like set.rbegin()
I remember it like this:
In the comparator function for priority queue, use conditions just as you would in custom sorting comparator for a vector.
Since you already know its max heap by default, just check out some implementations in the internet. You will know that the maximum (or minimum) element is always at the last position of the array in case of max heap (or min heap). That is why when you use greater() last element is minimum which is the topmost (highest priority) in the min heap.
Yes, you are right. I did that few hour ago and now everything makes sense. I don't know why the idea of checking the implementation crossed so late in my mind. Thanks anyways, for the helping hand.
The problem occured in the previous contest for the D question where I tried to use pq and customize its comparator. Didn't work out and I reversed all the conditions in frustration and boom...it got accepted
Where can I check internal implementation of priority queue?
In the version of GCC I have, it is located in /usr/include/c++/9/bits/stl_queue.h and /usr/include/c++/9/bits/stl_heap.h.
Thanks a lot!
I thought there is a website for checking implementations so I was searching the web.
Yep, github (for gcc at least)
one
two