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(max heap) 的默认行为是在顶部保存最大值，在我看来std::greater应该用于最大堆创建而不是最小堆创建

Answer 1

逻辑论证如下

1. std::priority_queue是容器适配器；pop_back()基本的内存考虑使后面成为push_back()序列容器（例如std::vector.
2. 原priority_queue语基于std::make_heap(constructor)、std::pop_heap+ container::pop_back( priority_queue::pop) 和container::push_back+ std::push_heap( priority_queue::push)
3. pop_heap将把底层存储的前面，放在后面，之后恢复堆不变。反之亦然push_heap。
4. sort_heap在 a 上执行（max_heap最初最大值位于前面）将重复从前面弹出并根据less（这是默认的比较运算符）对范围进行排序
5. 因此， a 的首选实现max_heap是将最大元素 wrtless放在前面，通过priority_queue::top(underlying container::front) 访问。
6. priority_queue人们仍然可以争论使用std::less比较器表示 a是否直观max_heap。它可以min_heap通过在调用各种堆函数的任何地方通过反转比较器的参数来定义（但请参阅@TC 的评论，使用 C++98 绑定器，这是相当冗长的）。一个（对我来说）违反直觉的结果是top()不会给予最高优先级的元素

Answer 2

C++ 堆函数make_heap,push_heap和pop_heap在最大堆上运行，这意味着当使用默认比较器时，顶部元素是最大值。因此，要创建最小堆，您需要使用greater<T>而不是less<T>.

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

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

Answer 3

请参阅http://en.cppreference.com/w/cpp/container/priority_queue。Apriority_queue旨在将最大值放在顶部。如果您使用默认std::less比较器，则会发生这种情况。因此，如果您想要反向行为，则需要使用反向比较器std::greater.