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

Question

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)?Should i implement the heap data structure from scratch for this 'delete' functionality?

If you need to remove arbitrary elements from a container, then perhaps a queue is not the right choice? How about a `std::deque` that you do sorted insertions on? You could easily wrap it up in a container-adapter with a similar interface to `std::priority_queue`. — Some programmer dude, May 22 '20 at 11:22
btw `std::vector` is a much better default than "implement from scratch". It doesn't have O(log n) erase, but it has O(0) complexity for getting the implementation right ;) — 463035818_is_not_an_ai, May 22 '20 at 11:32

score 1 · Accepted Answer · answered May 22 '20 at 11:31

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

No.

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

By using another container. std::set is the simplest compromise. A custom heap implementation may be more optimal.

score 0 · Answer 2 · answered May 22 '20 at 12:50

There is no inbuilt function for deleting a given element(other than top element) in priority queue.

I would recommend you to use std::set which performs the operations in O(logN) by implementing binary tree. But in case you need more better time complexity use std::unordered_set which performs operations in O(1) time and uses hashing.

So my advice will be that use std::set or std::unordered_set & don't restrict yourself to priority queue only.

lurscher · Answer 3 · 2021-10-30T04:37:38.230

As suggested by this solution, you can do something like this:

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;
       }
   }
};

This is specially useful when you need to take elements that are close to the top but are not exactly the top.

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

3 Answers3