Pie-Lie-Die's blog

Help in priority_queue with comparator.
By Pie-Lie-Die, history, 4 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I remind it as: priority_queue.top() works like set.rbegin()

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I remember it like this: 

The top of the heap is at the end of the vector.

In the comparator function for priority queue, use conditions just as you would in custom sorting comparator for a vector.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I check internal implementation of priority queue?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot!

      I thought there is a website for checking implementations so I was searching the web.

      → Reply