在C++中删除优先级队列中除顶级元素以外的其他元素

Question

在C++ STL的优先级队列类中，是否有任何内置的函数可以删除一个给定的元素（除了顶元素）？如果没有，如何在O(log n)中删除它？我是否应该为这个 "删除 "功能从头开始实现堆数据结构？

Answer 1

在C++ STL的优先级队列类中，是否有删除给定元素（除顶元素外）的内置函数？

没有。

如果没有，如何在O(log n)内删除它？

通过使用另一个容器。std::set 是最简单的折中方案。自定义堆的实现可能是更理想的。

Answer 2

在优先级队列中，没有内置的删除给定元素(除了top元素)的函数。

我建议你使用 std::set 的操作，它在 O(logN) 通过实现二进制树。但如果你需要更多更好的时间复杂度，可以使用 std::unordered_set 它在 O(1) 时间，并使用哈希。

所以我的建议将是，使用 std::set 或 std::unordered_set ＆amp;不要只局限于优先队列。