How to remove element not at top from priority_queue?
C++StlPriority QueueBinary HeapC++ Problem Overview
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.
C++ Solutions
Solution 1 - C++
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 - C++
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 - C++
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 - C++
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.
Solution 5 - C++
> 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);
}