在 C++ 中删除除顶部元素之外的优先级队列中的元素

Question

在 C++ STL 的优先级队列 class 中是否有任何内置函数可以删除给定元素（顶部元素除外）？如果不是，如何在 O(log n) 中删除它？我应该从头开始实现堆数据结构以实现此 'delete' 功能吗？

Answer 1

Is there any inbuilt function for deleting a given element (other than top element) in priority queue class of C++ STL?

没有

If not how to delete it in O(log n)?

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

Answer 2

没有用于删除优先级队列中给定元素（顶部元素除外）的内置函数。

我建议您使用 std::set 执行 中的操作O(logN) 通过实现二叉树。但是，如果您需要更好的时间复杂度，请使用 std::unordered_set 在 [=16 中执行操作=]O(1) 时间并使用散列。

所以我的建议是使用 std::set 或 std:: unordered_set 不要将自己局限于优先级队列。

Answer 3

作为 suggested by this solution，您可以这样做：

template<typename T>
class custom_priority_queue : public std::priority_queue<T, std::vector<T>>
{
  public:

    template< typename UnaryPredicate >
    T pop_match_or_top(UnaryPredicate p) {
        auto it = std::find_if(this->c.begin(), this->c.end(), p);
        if (it != this->c.end()) {
            T value = std::move(*it);
            this->c.erase(it);
            std::make_heap(this->c.begin(), this->c.end(), this->comp);
            return value;
       }
       else {
            T value = this->top();
            this->pop();
            return value;
       }
   }
};

当您需要获取靠近顶部但不完全是顶部的元素时，这特别有用。

在 C++ 中删除除顶部元素之外的优先级队列中的元素

Deleting element in priority queue other than top element in C++

c++

heap

stl

priority-queue

data-structures