c++ - 为什么 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 排序中总是使用较少。
2. push_back() 或 pop_back() 比 push_front() 或 pop_front() 更有效。