CODEWITHSUNDEEP
c++stlpriority-queue
mar
mar

Reputation: 232

Why does std::priority_queue use max heap instead of min heap?

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.

Upvotes: 11

Views: 3847

Answers (3)

Hisham Hijjawi
Hisham Hijjawi

Reputation: 2415

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.

Upvotes: 0

Dengzhi Zhang
Dengzhi Zhang

Reputation: 127

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().

Upvotes: 5

Chris Jefferson
Chris Jefferson

Reputation: 7157

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.

Upvotes: 1

Related Questions