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

Question

我想知道为什么使用the创建一个最小堆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

C++堆函数make_heap,push_heap并pop_heap在最大堆上运行,这意味着使用默认比较器时top元素是最大值.因此,要创建一个min-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 2

逻辑论证如下

1. std::priority_queue是一个容器适配器; 基本的内存考虑使后面成为序列容器修改(用pop_back()和push_back())的首选位置std::vector.
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. sort_heap在a上做max_heap(最初在前面有最大值)将反复弹出前面到后面并根据less(这是默认的比较运算符)对范围进行排序
5. 因此,a的优选实现max_heap是less在前面具有max元素wrt ,通过priority_queue::top(底层container::front)访问.
6. 一个仍然可以讨论是否直觉告诉我们,priority_queue有一个std::less比较器表示max_heap.它本来可以被定义为min_heap通过在各种堆函数的调用中反转比较器的参数(但是看看@TC的注释,C++ 98绑定器,这是相当冗长的).一个(对我来说)反直觉的结果就是那个top()没有给予元素最高优先级的结果