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

Question

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

Answer 1

在英语中，优先权更大的事情应该首先发生。因此，在优先级队列中，应首先弹出具有更高优先级的内容。

基本上，你的问题的答案是因为“优先级”这个词的定义强烈地暗示了从大到小的顺序。

试想医院大堂的优先轮候队伍，最优先（急症）的病人应该排在轮候治疗的最前面。

Answer 2

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

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

当然，您始终可以使用更大的而不是更少的来实例化priority_queue以获得您想要的行为。

Answer 3

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

< li >在所有默认STL排序中，我们总是使用较少的。 < li>push_back()或pop_back()比push_front()或pop_front()效率高得多。