为什么大多数语言都提供最小堆而不是最大堆实现？

Question

我只是注意到了一些事情，我想知道这是否有任何原因。除了C++ (std::priority_queue是一个最大堆)之外，我不知道有任何其他语言可以提供最大堆。

Python的heapq模块在列表的顶部实现了一个二进制的min堆。Java的库包含一个PriorityQueue类，它实现了一个最小优先级队列.Go的库包含一个容器/堆模块，它在任何兼容的数据结构之上实现最小堆。苹果的核心基础框架包含一个CFBinaryHeap结构，它实现了一个min堆。

我发现最大堆比最小堆更直观，而且我认为技术上的实现差异只是一个更改比较操作符的问题。有什么真正的理由吗？大多数应用程序需要一分钟而不是最大堆？提前感谢

Answer 1

正如其他人所观察到的，如果堆接受一个比较器，那么获得一种或另一种行为并不太困难。然而，快速阅读Google代码，就会发现min-堆在实际代码中更为普遍，因为有两个应用程序一次又一次地出现。

• Dijkstra/A*/许多其他最短路径算法(因为部分路径变得更长)。
• 事件模拟(因为时间在前进)。

此外，我认为，由于默认排序返回的项从小到大，默认堆也应如此。

Answer 2

这只是品味的问题。我不认为会有任何具体的原因。这就像有些人喜欢用最小化成本来表达优化问题，而另一些人则喜欢说利润最大化。

Answer 3

我知道的大多数语言都允许传递一个参数来决定它应该是最小堆还是最大堆。因此，默认值有些任意性。我想对于大多数语言来说，定义默认运算符是一个一致性问题。对于stl中的C++，缺省值是std::less，导致一个min堆。

对于默认的everywhere使用std::less的一致性意味着您只需要在使用任何类型的数据结构时实现这种比较，而不必在以后设计类时决定要使用哪种数据结构。我想其他语言也是一样的，唯一的区别是一个比比较更大的标准。