-1

Why does priority_queue use greater<> for ascending order?

Since sort() method in c++ STL uses greater<>() as a third parameter to make descending order it's confusing for me that priority_queue uses greater<> for the opposite order.

Why and How does it work this way? I don't understand how the same greater structure behaves different depending on where it is used.

sort<temp.begin(),temp.end(),greater<>()>; // -> descending order priority_queue<int,vector<int>,greater<int>>; // -> ascending order
Improve this question
3
  • 1
    Side note: Priority queues are built upon heaps, which use std::less to allow new elements to "sink" down in the heap. This, however, brings the largest element to the top of the heap. In order to get the smallest element to rise to the top of the heap, you have to use std::greater. Commented Feb 21, 2024 at 3:51
  • Sidenote: priority_queue is not technically "ordered" Commented Feb 21, 2024 at 3:56
  • An educated guess: (History experts can correct me!) Long ago, a decision was made that std::less and < should be the default for all comparitors in the Standard Library. I am no expert, but I believe that is still true today. When std::priority_queue was designed, it made sense that the element with the highest priority should be first out of the queue. So, std::priority_queue was crafted so that it could use std::less to output the "biggest" element. To get the smallest, you have to invert the comparison. Commented Feb 21, 2024 at 4:23

1 Answer 1

Reset to default
2

You're thinking incorrectly about the meaning of a priority queue. When you remove an item from a priority queue, you are removing the highest priority item. Yes, a priority queue uses an ordering functor, but that ordering functor only says which item has the higher priority.

You should not think of the ordering functor as "sorting"; it simply compares the relative priority of the elements.

the same greater structure

They don't have "the same greater structure". sort is an algorithm; it operates on a sequence of elements. priority_queue is a container-adapter; it is a sequence of elements. sort does a thing once and then it's over. priority_queue is the thing.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.