std::priority_queue 和 make_heap API 设计
std::priority_queue and make_heap API design
我正在阅读 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（最小元素在顶部）。如果（父比较器子项）为真，我会期望最大堆，因为定义了堆排序（在我读过的所有文献中）。
我发现这种 API 设计令人困惑。
有没有理由这样定义它？
这是让您动脑筋的事情 - 提供 std::greater 实际上会产生最小堆。
原因如下：从堆的角度来看，比较器在堆上定义了小于关系，即使它实际上在做其他事情。当std::priority_queue需要插入元素时，它调用比较器并给它两个元素。如果比较器 returns true，它认为第一个元素小于第二个元素，并将第二个元素放在前面（因为 std::priority_queue 是一个 max 堆 实施）。结果，您最终得到了最小堆。
我也觉得很困惑，但从不同的角度来看。假设您要按升序对序列进行排序。有几种方法可以做到：
- 使用
std::less 将您的数据放入 std::vector 或 std::deque 和 运行 std::sort() 中。 =51=]
- 使用
std::less. 将数据放入 std::list 和 运行 std::list::sort()
- 将您的数据插入配置为
std::less 的 std::set 中，最后它会自动排序。
- 将您的数据放入
std::vector 或 std::deque 和 运行 std::make_heap() 中，然后是 std::pop_heap()-s 使用 std::less.
- 使用
std::greater 通过 std::priority_queue 推送您的数据 (!!!).
正如我们所见，从这个角度来看，std::priority_queue 是一个明确的异常值。
实际上，std::priority_queue 在这方面令人困惑的行为背后的原因隐藏在第 (4) 项中，因为那是 std::priority_queue 在下面所做的。 (4) 也违背了我的直觉（尽管程度较小），因为在中间状态（虽然并非所有 std::pop_heap 都已执行）序列的排序部分在其上限范围内，而不是下限范围。
但这也解释了为什么为标准库选择了最大堆 - std::pop_heap 将弹出的元素放在可以在恒定时间内从中移除的位置，而不管使用的容器类型如何。
我正在阅读 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（最小元素在顶部）。如果（父比较器子项）为真，我会期望最大堆，因为定义了堆排序（在我读过的所有文献中）。
我发现这种 API 设计令人困惑。
有没有理由这样定义它？
这是让您动脑筋的事情 - 提供 std::greater 实际上会产生最小堆。
原因如下：从堆的角度来看，比较器在堆上定义了小于关系，即使它实际上在做其他事情。当std::priority_queue需要插入元素时，它调用比较器并给它两个元素。如果比较器 returns true，它认为第一个元素小于第二个元素，并将第二个元素放在前面（因为 std::priority_queue 是一个 max 堆 实施）。结果，您最终得到了最小堆。
我也觉得很困惑，但从不同的角度来看。假设您要按升序对序列进行排序。有几种方法可以做到：
- 使用
std::less将您的数据放入std::vector或std::deque和 运行std::sort()中。 =51=] - 使用
std::less. 将数据放入 - 将您的数据插入配置为
std::less的std::set中，最后它会自动排序。 - 将您的数据放入
std::vector或std::deque和 运行std::make_heap()中，然后是std::pop_heap()-s 使用std::less. - 使用
std::greater通过std::priority_queue推送您的数据 (!!!).
std::list 和 运行 std::list::sort()
正如我们所见，从这个角度来看，std::priority_queue 是一个明确的异常值。
实际上，std::priority_queue 在这方面令人困惑的行为背后的原因隐藏在第 (4) 项中，因为那是 std::priority_queue 在下面所做的。 (4) 也违背了我的直觉（尽管程度较小），因为在中间状态（虽然并非所有 std::pop_heap 都已执行）序列的排序部分在其上限范围内，而不是下限范围。
但这也解释了为什么为标准库选择了最大堆 - std::pop_heap 将弹出的元素放在可以在恒定时间内从中移除的位置，而不管使用的容器类型如何。