CODEWITHSUNDEEP
c++data-structuresstlheappriority-queue
Praneethreddy Mallupally
Praneethreddy Mallupally

Reputation: 17

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

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?

Upvotes: 1

Views: 3690

Answers (3)

lurscher
lurscher

Reputation: 26943

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.

Upvotes: 0

Lucas
Lucas

Reputation: 71

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.

Upvotes: 0

eerorika
eerorika

Reputation: 238311

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.

Upvotes: 1

Related Questions