How to remove element not at top from priority_queue?

Question

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.

Answer 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()) {
              return false;
          }
          if (it == this->c.begin()) {
              // deque the top element
              this->pop();
          }    
          else {
              // remove element and re-heap
              this->c.erase(it);
              std::make_heap(this->c.begin(), this->c.end(), this->comp);
         }
         return true;
     }
};

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

Answer 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);

Answer 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).

Answer 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.

Answer 5

Please note the following approach does the things but not the optimized way to solution. For optimized approach, check other answers.

Let you want to delete the 5th element in the priority_queue<type> Q . Then you can do this like:

vector<type> tempQ;
int i = 0;
int n = 5;
type t;

// backup n-1 items
while(i < n-1)
{
    tempQ.push_back(Q.top());
    Q.pop();        
    i++;
}

// remove the nth item
Q.pop();

// restore the backed up items
i = 0;
while(i < n-1)
{
    t = tempQ[i++];
    Q.push(t);
}