std:：priority_queue和make_heap API设计

Question

我正在阅读priority_queue(基本上是make_heap的包装器)的文档，它发现可以用比较函数定制它。

来自文档(http://en . CP preference . com/w/CPP/container/priority _ queue):

可以提供用户提供的Compare来更改排序，例如使用std::更大会导致最小的元素显示为top（）。

在维基百科和其他CS文本中，堆被定义为这样的：

在计算机科学中，堆是一种特殊的基于树的数据结构，它满足堆属性：如果A是B的父节点，那么节点A的键（值）相对于节点B的键排序，并且在整个堆中应用相同的排序。堆可以进一步分为“最大堆”或“最小堆”。在最大堆中，父节点的键总是大于或等于子节点的键，最高键在根节点中。

但是在std::priority_queue实现中，提供std::更大会导致创建一个MinHeap（顶部的最小元素）。如果（父比较子级）为真，我会期望最大堆，因为堆顺序是定义的（在我读过的所有文献中）。

我发现这种API设计令人困惑。

有理由这样定义它吗？

Answer 1

这是需要考虑的事情——提供< code>std::greater实际上会产生min heap。

这样做的原因如下：从堆的角度来看，比较器的定义小于堆上的关系，即使它实际上是在做其他事情。当std::priority_queue需要插入元素时，它会调用比较器并给它两个元素。如果比较器返回true，它会认为第一个元素小于第二个元素，并将第二个元素放在首位（因为std::priority_queue是最大堆实现）。因此，您最终得到了最小堆。

Answer 2

我也发现它令人困惑，但从一个有点不同的角度来看。假设您要按升序对序列进行排序。有几种方法可以做到这一点：

< li >将数据放入< code>std::vector或< code > STD::dequee 中，并使用< code>std::less运行< code>std::sort()。 < li >将数据放入< code>std::list中，并使用< code>std::less运行< code>std::list::sort()。 < li >将您的数据插入用< code>std::less配置的< code>std::set中，最后它会自动排序。 < li >将数据放入< code>std::vector或< code > STD::dequee 中，运行< code>std::make_heap()，然后使用< code>std::less运行< code>std::pop_heap()-s。 < li >使用< code>std::greater (!！！).

如我们所见，std:：priority_queue从这样的角度来看是一个明确的异常值。

实际上，std::priority_queue在这方面令人困惑的行为背后的原因隐藏在第（4）项中，因为这就是std::priority_queue在下面所做的事情。（4）也违背了我的直觉（尽管在较小程度上），因为在中间状态下（虽然不是所有的std::pop_heap都已执行）序列的排序部分在其上范围，而不是下范围。

但它也解释了为什么为标准库选择了最大堆-＜code＞std：：pop_。