How to remove element not at top from priority_queue?

69,579

Solution 1

The standard priority_queue<T> can be customized through inheritance. It has protected members c and comp that can be referenced in a descendant class.

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

      bool remove(const T& value) {
        auto it = std::find(this->c.begin(), this->c.end(), value);
        if (it != this->c.end()) {
            this->c.erase(it);
            std::make_heap(this->c.begin(), this->c.end(), this->comp);
            return true;
       }
       else {
        return false;
       }
 }
};

void main()
{
   custom_priority_queue<int> queue;

   queue.push(10);
   queue.push(2);
   queue.push(4);
   queue.push(6);
   queue.push(3);

   queue.remove(6);

   while (!queue.empty())
   {
      std::cout << queue.top();
      queue.pop();

      if (!queue.empty())
      {
        std::cout << ", ";
      }
   }

 }

Output:

10, 4, 3, 2

Solution 2

The best solution is to use std::set. Sets provide methods which allow it to be used both as a min/max heap (or a priority queue).

std::set<int> pq;

//accessing the smallest element(use as min heap)
*pq.begin();

//accessing the largest element (use as max heap)
*pq.rbegin();

Furthermore sets also allow random deletion.

//to delete the integer '6'
auto it = pq.find(6);
pq.erase(it);

Solution 3

A neat little trick to handle deletes for a priority_queue STL - use another priority_queue, say, del_pq. Keep inserting all the delete values to this. When you are popping values from the original priority queue, check with top of del_pq and see if we wanted to delete it. If it matches, delete the value from the original priority_queue.

This method implements a way to lazily delete the values in our original priority queue. Can take up twice the memory, but average delete and inserts remain O(logN).

Solution 4

Pradip and MASh sacrifice the time to realize the remove operation. But if time complexity is important to you, I suggest you to use hash min_heap. A Hash table stores the value-pointer and the pointers point to a min_heap. Which means you can spend O(1) time to find the value in min_heap and O(log(n)) to remove(sift-up or sift down) the element.

Share:
69,579
ishan3243
Author by

ishan3243

Updated on July 09, 2022

Comments

  • ishan3243
    ishan3243 almost 2 years

    In my program I need to delete an element from a priority queue that is not at the top. Can that be done? If not, please suggest a way to do so except creating your own heap.

  • klaus triendl
    klaus triendl almost 8 years
    The call to make_heap isn't necessary since the heap remains ordered.
  • Sandeep Tuniki
    Sandeep Tuniki over 7 years
    @alexm If I want to pass a custom comparator to the object, how do I write the class declaration?
  • kevin
    kevin over 7 years
    So what is the complexity of this method ? I do not see the need of using a temporary PQ. why not use a vector vector<type> tempQ
  • Shafi
    Shafi over 7 years
    Good point, here we just need a container. I using a vector instead will improve time complexity. I updated the answer. +1 for your point @kevin
  • Manfred Urban
    Manfred Urban about 7 years
    @SandeepTuniki: If you want to pass a custom comparator, the class declaration could look like this: template<typename T, class Container=std::vector<T>, class Compare=std::less<typename Container::value_type>> class custom_priority_queue : public std::priority_queue<T, Container, Compare>
  • Jon Deaton
    Jon Deaton over 6 years
    Never sacrifice the time.
  • Aelian
    Aelian over 5 years
    @klaustriendl, could you explain why make_heap is unnecessary, especially if the removed item happen to be at the top / multiple items were removed? My guess is that make_heap is unnecessary only if heap is fully sorted which is not the case.
  • klaus triendl
    klaus triendl about 5 years
    @Aelian You are absolutely right, and thank you for detecting my mistake. It seems I misunderstood the properties of a heap, so I mistakened "sorted" for "structured". So if you remove an element you need to restructure the heap.
  • Vipul Jain
    Vipul Jain almost 5 years
    This solution won't work if the elements can repeat.
  • Po-Jen Lai
    Po-Jen Lai over 4 years
    I think the idea is cool, you can use multiset for repeating elements. But remember to pay attention when you are erasing by value instead of iterator.
  • Yasser Hussain
    Yasser Hussain almost 3 years
    For repeated elements you can simply use a map. Just keep a count of keys and when the count of a key becomes 0, remove the key. Solved this problem using the same idea spoj.com/problems/ARRAYSUB
  • foddex
    foddex about 2 years
    you could check if "it" equals this->c.begin(), if not, no need to call make_heap after erase()