11

I always wondered why STL priority queue uses max heap instead of min heap by default. Two obvious use cases that come to mind is pathfinding (Dijkstra) and building Huffman codes. Both algorithms need to pull min elements first. Since sorting (std::sort) uses ascending order by default, I wonder what was the design reasoning behind priority_queue, because I would very much prefer a min heap by default.

Improve this question
4
  • 1
    Because it's fundamentally a priority queue, not a heap. Commented Aug 31, 2014 at 9:18
  • 2
    Probably it was because in a priority queue you want higher priority items to come first, but I agree that it was not a well-considered design (as it effectively requires everyone to implement their comparators backwards). It would have made more sense to have some sort of priority object that implemented its comparison operators such that the higher priority value was "less than" the lower priority values, instead. Commented Aug 31, 2014 at 9:19
  • @MichaelAaronSafyan: even "priority" is confusing, because people say things like "this task is priority 1" they mean "do it first" not "do it last." The layman's understanding of priority is that "top" priority is the smallest number, and "second" priority comes next.... I agree with the OP that the choice made in the STL seems silly, but perhaps no one here truly knows why it was made this way. Commented Aug 31, 2014 at 11:28
  • Related: The reason of using std::greater for creating min heap via priority_queue. Commented Apr 24 at 3:58

3 Answers 3

Reset to default
4

Priority_queue is adapted from make_heap/pop_heap/push_heap/sort_heap. When you make_heap with less, the elements are sorted ascending. And the last element is treated as root element. So it is max heap. I guess there are two reasons:

  1. We always use less in all default STL sorting.
  2. push_back() or pop_back() is much more efficient than push_front() or pop_front().
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You answered my wonder also
"When you make_heap with less, the elements are sorted ascending. And the last element is treated as root element." That's not how heaps work; see binary heap for explanation.
2

There is a reason, but it is to do with the interconnected features of C++.

priority_queue was designed to be an easy-to-use wrapper around make_heap, pop_heap and push_heap. It makes sense for the heap functions to keep the largest value at the front, because that is what you need to be able to implement sort_heap, which also use the heap functions.

Of course, you can always instantiate priority_queue with greater rather than less to get the behaviour you want.

Improve this answer

1 Comment

Then, why make_heap makes max heap rather than min heap by default? In fact, sort_heap can be implemented by either max heap or min heap.
0

In the English language, something with a larger priority should happen first. Therefore, in a priority queue, something with a higher priority should be popped first.

Basically the answer to your question is because the definition of the word priority strongly implies ordering from largest to smallest.

Just imagine a priority queue like a hospital lobby. Patients with the largest priority (urgent cases) should be a the front of the queue for treatment.

Improve this answer

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.