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

Question

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

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

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

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

Answer 1

逻辑论证如下

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