Why does std :: priority_queue use the maximum heap instead of the minimum heap?
I've always wondered why the STL priority queue uses the maximum heap and not the minimum heap by default. Two obvious use cases that come to mind are the (Dijkstra) path and the construction of Huffman codes. Both algorithms must first output the minimum elements. Since sorting (std :: sort) is ascending by default, I wonder what the design was based on priority_queue, because I would have preferred the default minimal heap.
source to share
There is a reason, but it has to do with C ++ related features.
priority_queue
was designed as an easy-to-use wrapper around make_heap
, pop_heap
and push_heap
. For heap functions, it makes sense to keep the largest value up front, because that's what you need to implement sort_heap
, that use heap functions as well.
Of course, you can always create priority_queue
with greater
, not less
to get the behavior you want.
source to share
Priority_queue adapts from make_heap / pop_heap / push_heap / sort_heap. When you make_heap smaller, the items are sorted in ascending order. And the last element is considered as the root element. So this is the maximum heap. I think there are two reasons:
- We always use less in all standard STL collations.
- push_back () or pop_back () is much more efficient than push_front () or pop_front ().
source to share