为什么std :: priority_queue使用最大堆而不是最小堆？

Question

我一直想知道为什么STL优先级队列默认使用最大堆而不是最小堆。想到的两个明显的用例是寻路（Dijkstra）和构建霍夫曼代码。两种算法都需要先提取最小元素。由于排序（std :: sort）默认情况下使用升序，因此我想知道priority_queue背后的设计原因是什么，因为默认情况下我非常喜欢最小堆。

Answer 1

Priority_queue 改编自 make_heap/pop_heap/push_heap/sort_heap。当您使用 less 来 make_heap 时，元素将按升序排序。最后一个元素被视为根元素。所以它是最大堆。我想有两个原因：

1. 我们在所有默认的 STL 排序中总是使用 less。
2. push_back() 或 pop_back() 比 push_front() 或 pop_front() 效率更高。

Answer 2

这是有原因的，但这与 C++ 的互连特性有关。

priority_queue被设计为一个易于使用的围绕make_heap,pop_heap和 的包装器push_heap。堆函数将最大值保留在前面是有意义的，因为这是您需要能够实现的sort_heap，它也使用堆函数。

当然，您始终可以实例化priority_queue而greater不是less获得您想要的行为。