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.

Hereunto

Why a have you specifically chosen a priority queue if it doesn't support the operations you want? Why not instead choose a data structure which does support those operations, like a set? – Dottydoty

@Benjamin Lindley because i need both behaviors. – Hereunto

Which behaviors? Fast access to the max (or min) element? set has that. Quick removal of arbitrary elements? set has that too. – Dottydoty

@Benjamin Lindley oh really!! i didn't know that....i'll check :) – Hereunto

@Benjamin Lindley but sets have unique elements and i need duplicate elements – Hereunto

Then use a multiset. – Dottydoty

@Benjamin Lindley if i am not wrong multisets are implemented as BST right? – Hereunto

@Benjamin Lindley i am not able to find out how to get the min/max in multiset.....could you please tell me? – Hereunto

*mySet.begin(), *mySet.rbegin(). Since a set is ordered, the first and last elements are the smallest and the largest, correspondingly. – Stanfordstang

Following SO post also having same problem you can refer it. #3076663 – Graveyard

possible duplicate of STL Priority Queue - deleting an item – Perambulate

One could also use a set of pairs (item, i), where i as an integer increased for every item. Then the elements appear unique. One has to store the i value in the item without it affecting the comparator. – Tandi

@Hereunto This question still shows up as unanswered. Wasn't alexm's answer spot on? – Domiciliate

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

Liz

The call to make_heap isn't necessary since the heap remains ordered. – Sapor

@Liz If I want to pass a custom comparator to the object, how do I write the class declaration? – Kendre

@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> – Etz

@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. – Savick

@Savick 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. – Sapor

you could check if "it" equals this->c.begin(), if not, no need to call make_heap after erase() – Sweeny

@Sweeny : added special case when the found item is on the top of the queue. – Liz

need private inheritance here, from obvious reasons of deleting base* w/o virtual dtor – Tsana

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

Gaelic

This solution won't work if the elements can repeat. – Ladner

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. – Agglomerate

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 – Vocabulary

@VipulJain You could always use a multi-set. – Cacoepy

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

Acroterion

I am not sure if the element at the top is always the answer, but using unordered_set (or similar) for the deletion should also work in sublinear time. – Expanded

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.

Margitmargo

Never sacrifice the time. – Bordie

Answer 5

My C++ is quite rusty - here I provide a C# solution that I hope can be easily translated to C++.

The idea is to subclass the standard C# class PriorityQueue and add a Remove method. Here is the code - for readability I am using an instance of PriorityQueue<int, int> - this could be easily generalized to PriorityQueue<TElement, TPriority>

    public class MyHeap 
    {
        private PriorityQueue<int, int> _theQueue = new PriorityQueue<int, int>();
        private HashSet<int> _deleted = new HashSet<int>();

        public void Add(int v)
        {
            _deleted.Remove(v);
            _theQueue.Enqueue(v, v);
        }

        public void Remove(int v)
        {
            _deleted.Add(v);
        }

        public int GetMinimum()
        {
            var qMin = _theQueue.Peek();
            while(_deleted.Contains(qMin))
            {
                _theQueue.Dequeue();
                _deleted.Remove(qMin);
                qMin = _theQueue.Peek();
            }
            return qMin;
        }
    }

Notorious

Answer 6

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

Dogtooth

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 – Redness

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 @Redness – Dogtooth