通过 `priority_queue` 使用 `std::greater` 创建最小堆的原因

Question

我想知道为什么要使用 priority_queue 创建最小堆，应该使用 std::greater？

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;

对我来说，因为最小值总是位于堆的顶部，所以使用的class应该是std::less

更新： 另一方面，由于 priority_queue （最大堆）的默认行为是在顶部保持最大值，在我看来 std::greater 应该用于最大堆的创建而不是用于最小堆创建

Answer 1

C++ 堆函数 make_heap、push_heap 和 pop_heap 对 max heap 进行操作，这意味着顶部元素是 maximum 使用默认比较器时。因此，要创建最小堆，您需要使用 greater<T> 而不是 less<T>。

我怀疑使用最大堆而不是最小堆是因为使用 less 操作更容易实现。在 C++ 中，less 具有作为所有 STL 算法的 "default" 比较器的特殊特权；如果你只打算执行一个比较操作（除了 ==），它应该是 <。这导致了不幸的怪癖，即 priority_queue<T, C<T>, less<T>> 表示最大队列而 priority_queue<T, C<T>, greater<T>> 表示最小队列。

此外，某些算法如 nth_element 需要最大堆。

Answer 2

参见http://en.cppreference.com/w/cpp/container/priority_queue。 A priority_queue 旨在将最大值放在顶部。如果您使用默认的 std::less 比较器，就会发生这种情况。所以如果你想要反向行为，你需要使用反向比较器，std::greater.

Answer 3

逻辑论证如下

std::priority_queue是容器适配器；基本的内存考虑使背面成为序列容器（如 std::vector）修改的首选位置（使用 pop_back() 和 push_back()）。
priority_queue 基元基于 std::make_heap（构造函数）、std::pop_heap + container::pop_back (priority_queue::pop) 和 container::push_back + std::push_heap (priority_queue::push)
pop_heap会把底层存储的前面，放到后面，恢复堆不变性然后。 push_heap.
在 max_heap 上执行 sort_heap（最初最大值在前面）将 repeatedly pop the front to the back 并根据 less 对范围进行排序（这是默认比较运算符）
因此，max_heap 的首选实现是拥有最大元素 w.r.t。 less 在前面，通过 priority_queue::top 访问（底层 container::front）。
人们仍然可以争论 priority_queue 与 std::less 比较器代表 max_heap 是否直观。它可以通过反转比较器的参数来定义为 min_heap（但请参阅@T.C 的评论。对于 C++98 绑定器，这相当冗长）在对各种堆的调用中随处可见职能。一个（对我来说）违反直觉的结果是 top() 不会给元素 top priority

通过 `priority_queue` 使用 `std::greater` 创建最小堆的原因

The reason of using `std::greater` for creating min heap via `priority_queue`

c++

heap

priority-queue

min-heap

c++11