C ++标准库中是否有maxheap？

Question

我知道std::priority_queue该类实现了最小堆。有没有办法将其用作最大堆？还是有替代的Maxheap结构？我知道我可以std::make_heap()在std::vectorlambda 上使用该函数来创建自己的Maxheap，但是随后使用诸如std::pop_heap()怪异的函数，并且我认为它们不易于使用。应该有一种更简单的方法，就像我认为的min_heap（priority queue）。

Answer 1

简答

最大堆：

priority_queue<int> maxHeap; // NOTE: default is max heap

最小堆

priority_queue<int, vector<int> , greater<int>> minHeap;

标头和命名空间：

#include <vector>
#include <priority_queue>

using namespace std;

Answer 2

关于std::priority_queue：

Compare可以提供用户提供的更改顺序，例如使用std::greater<T>会导致最小的元素显示为top()。

由于std::less<T>是template参数的默认模板Compare参数，因此默认情况下它已经是最大堆。如果要使用最小堆（上面的引用所建议的内容），请传递std::greater<T>而不是std::less<T>作为模板参数。

总结一下：

• 最大堆数：通过std::less<T>（这是默认的模板参数）。
• 敏堆：通过std::greater<T>。

请注意，std::priority_queue它实际上是一个容器适配器（与数据结构相反）。它没有指定正在使用的底层数据结构。然而，由于操作的指定运行时间复杂度push()，pop()并且top()，它很可能为堆实现。