使用'std::更大'通过'priority_queue'创建最小堆的原因

Question

我想知道为什么使用priority_queue创建min堆时，应该使用std::more？

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

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

更新：另一方面，由于priority\u queue（max heap）的默认行为是在顶部保留最大值，因此在我看来，std:：greater应该用于最大堆创建，而不是最小堆创建

Answer 1

看见http://en.cppreference.com/w/cpp/container/priority_queue.优先级队列设计用于将最大值置于顶部。如果使用默认的std:：less比较器，就会发生这种情况。因此，如果需要反向行为，则需要使用反向比较器，std:：greater。

Answer 2

C堆函数make_heap、push_heap和pop_heap在最大堆上运行，这意味着使用默认比较器时，顶部元素是最大值。因此，要创建最小堆，需要使用greater

我怀疑使用最大堆而不是最小堆是因为使用less操作更容易实现。在C语言中，less有特权成为所有STL算法的“默认”比较器；如果您只打算实现一个比较操作（而不是=），那么它应该是

此外，某些算法，如nth\u元素需要最大堆。

Answer 3

逻辑论点如下

1. std:：priority_queue是一个容器适配器；对于序列容器（如std:：vector），基本内存考虑使背面成为修改的首选位置（使用pop_back（）和push_back（））
2. priority\u queue原语基于std:：make\u heap（构造函数），std:：pop\u heapcontainer:：pop\u back（priority\u queue:：pop）和container:：push\u back（priority\u queue:：push）
3. pop_heap将占用底层存储的前面，并将其放在后面，然后恢复堆不变量。与之相反的是push\u heap
4. 在max\u heap上执行sort\u heap（最大值最初位于前面）将重复从前到后弹出，并根据less对范围进行排序（这是默认的比较运算符）
5. 因此，max_heap的首选实现是将max元素w.r.t.less放在前端，通过priority_queue:：top（底层container:：front）访问
6. 我们仍然可以争论，带有std:：less比较器的priority\u队列表示max\u堆是否直观。它可以通过反转比较器的参数来定义为min_heap（但请参见@T.C.的评论，对于C 98绑定，这相当冗长），在对各种堆函数的调用中无处不在。一个（对我来说）违反直觉的结果是top（）不会给元素赋予最高优先级