C++标准库中有maxheap吗？

Question

我知道 std::priority_queue class 实现了一个最小堆。有没有办法将其用作最大堆？或者是否有替代的 Maxheap 结构？我知道我可以在带有 lambda 的 std::vector 上使用 std::make_heap() 函数来创建我自己的 Maxheap 但是然后使用 std::pop_heap() 之类的函数很奇怪，我认为它们不容易使用.应该有一个更简单的方法，就像我认为的min_heap（优先队列）。

Answer 1

关于std::priority_queue：

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

由于 std::less<T> 是 Compare 模板参数的默认模板参数，默认情况下它已经是 max 堆 。如果你想要一个 min heap 而不是（上面引述的建议），传递 std::greater<T> 而不是 std::less<T> 作为模板参数。

总结：

最大堆：传递std::less<T>（这是默认模板参数）。
最小堆：通过 std::greater<T>.

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

Answer 2

没有"heap"容器就像没有"search tree"一样，也没有"hash map"（而不是后两者，有有序和无序的关联容器，它们在实践中实现使用这些数据结构，因为没有其他数据结构可以满足为这些容器指定的要求。

是一个容器适配器std::priority_queue，可以适配SequenceContainer（std::vector默认适配），提供与max/min heap 可以，并且可能在内部实现为某种堆。

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

Answer 3

简答

最大堆：

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

最小堆

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

Headers 和命名空间：

#include <vector>
#include <priority_queue>

using namespace std;

C++标准库中有maxheap吗？

Is there a maxheap in the C++ standard library?

c++

priority-queue

standard-library

c++-standard-library

max-heap