C标准库中有maxheap吗？

Question

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

原文由 OgiciBumKacar 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

关于 std::priority_queue ：

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

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

总结一下：

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

---

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

原文由 ローウ 发布，翻译遵循 CC BY-SA 4.0 许可协议