c++ - std::priority_queue 和 make_heap API 设计

Question

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

来自文档(http://en.cppreference.com/w/cpp/container/priority_queue):

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater would cause the smallest element to appear as the top().

在维基百科和其他 CS 文本中，堆是这样定义的:

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node.

但在 std::priority_queue 实现中，提供 std::greater 会导致创建 MinHeap(最小元素在顶部)。如果(parent comparator children)为真，我会期望最大堆，因为定义了堆顺序(在我读过的所有文献中)。

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

有没有理由这样定义它？

Answer 1

我也觉得很困惑，但从不同的角度来看。假设您要按升序对序列进行排序。有几种方法可以做到这一点:

1. 将您的数据放在 std::vector 中或 std::deque然后运行 ​​std::sort()使用 std::less .
2. 将您的数据放在 std::list 中然后运行 ​​std::list::sort()使用 std::less .
3. 将您的数据插入 std::set配置为 std::less 最后自动排序。
4. 将您的数据放在 std::vector 中或 std::deque然后运行 ​​std::make_heap()其次是 std::pop_heap() -s 使用 std::less .
5. 通过 std::priority_queue 推送您的数据使用 std::greater (!!!)。

正如我们所见，std::priority_queue从这样的角度来看，它绝对是异常值。

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

但这也解释了为什么为标准库选择最大堆 - std::pop_heap将弹出的元素放在可以在恒定时间内将其移除的位置，而不管使用的容器类型如何。