c++ - C++标准库中有maxheap吗？

Question

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

Answer 1

关于std::priority_queue：

可以提供用户Compare提供来更改排序，例如 usingstd::greater<T>将导致最小元素显示为top().

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

总结一下：

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

---

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

Answer 2

简答

最大堆：

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 3

没有“堆”容器，就像没有“搜索树”，也没有“哈希图”（而不是后两者，有有序和无序的关联容器，它们实际上是使用这些数据结构实现的，因为没有其他数据结构可以满足为这些容器指定的要求）。

有一个容器适配器std::priority_queue，它可以适配一个 SequenceContainer（std::vector默认适配），并提供与最大/最小堆相同的操作，并且可能在内部实现为某种堆。

还有std::make_heap一个可用于在随机访问范围内强制执行最大堆属性。