为什么std :: priority_queue使用max heap而不是min heap？
我总是想知道为什么STL优先级队列默认使用max堆而不是min堆。想到两个明显的用例是寻路（Dijkstra）和建立霍夫曼代码。这两种算法都需要先拉出最小元素。 默认情况下，由于排序（std :: sort）使用升序排列，所以我想知道priority_queue， 背后的设计原因是什么，因为默认情况下我非常喜欢min堆。为什么std :: priority_queue使用max heap而不是min heap？
有一个原因，但它是与C++的相互关联的功能。
priority_queue被设计为围绕make_heap,pop_heap和push_heap的易于使用的包装。堆函数将最大值保留在前端是合理的，因为这是您需要实现的功能sort_heap，它也使用堆函数。
当然，您可以始终使用greater实例化priority_queue而不是less以获得所需的行为。
那么，为什么'make_heap'默认情况下最大堆而不是最小堆？实际上，'sort_heap'可以通过max heap或min heap来实现。 – 2016-06-24 08:50:29
Priority_queue从make_heap/pop_heap/push_heap/sort_heap改编而来。当你使用更少的make_heap时，元素按升序排序。最后一个元素被视为根元素。所以它是最大的堆。我想有两个原因：
- 我们总是使用较少的所有默认STL排序。
- push_back（）或pop_back（）比push_front（）或pop_front（）效率高得多。
因为它基本上是*优先级队列*，而不是堆。 – 2014-08-31 09:18:37
可能是因为在优先级队列中，您希望优先级较高的项目先到达，但我同意这不是一个考虑周全的设计（因为它实际上要求每个人都向后执行比较）。相反，拥有某种优先级对象来实现其比较运算符会更有意义，因为较高优先级的值“低于”低优先级值。 – 2014-08-31 09:19:41
@MichaelAaronSafyan：即使“优先”也是令人困惑的，因为人们说“这项任务是优先考虑的事情1”，他们的意思是“先做”，而不是“最后做”。普通人对优先级的理解是，“最高”优先级是最小的优先级，接下来是“第二优先级”......我同意OP在STL中做出的选择似乎很愚蠢，但也许这里没有人真正知道*为什么这样做。 – 2014-08-31 11:28:02