How to remove element not at top from priority_queue?
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.
ishan3243
Updated on July 09, 2022Comments
-
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 almost 8 yearsThe call to
make_heap
isn't necessary since the heap remains ordered. -
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 over 7 yearsSo 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 over 7 yearsGood 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 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 over 6 yearsNever sacrifice the time.
-
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 thatmake_heap
is unnecessary only if heap is fully sorted which is not the case. -
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 almost 5 yearsThis solution won't work if the elements can repeat.
-
Po-Jen Lai over 4 yearsI 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 almost 3 yearsFor 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 about 2 yearsyou could check if "it" equals this->c.begin(), if not, no need to call make_heap after erase()