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 将获取底层存储的前面，并将其放在后面，之后恢复堆不变性。 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 优先级的元素