Removing a Specific Element from Priority Queue

The standard std::priority_queue in C++ does not provide a direct way to remove a specific element from the queue without popping the top element. The priority queue is designed to maintain the heap property and only allows access to the top element.

However, if you need to remove a specific element from a priority queue, you can achieve this by creating a new priority queue and selectively pushing elements from the original queue to the new one, skipping the element you want to remove.

Here's an example of how you can remove a specific element from a priority queue:

1#include <iostream>
2#include <queue>
3
4int main() {
5  std::priority_queue<int> pq;
6
7  pq.push(10);
8  pq.push(30);
9  pq.push(20);
10  pq.push(40);
11
12  int elementToRemove = 20;
13
14  std::priority_queue<int> newPq;
15
16  while (!pq.empty()) {
17    if (pq.top() != elementToRemove) {
18      newPq.push(pq.top());
19    }
20    pq.pop();
21  }
22
23  // The original priority queue is now empty
24  pq = std::move(newPq);
25
26  while (!pq.empty()) {
27    std::cout << pq.top() << " ";
28    pq.pop();
29  }
30}

In this example, we want to remove the element with value 20 from the priority queue. We create a new priority queue newPq and iterate over the original priority queue pq. For each element in pq, we check if it is not equal to the elementToRemove. If it's not, we push the element into newPq. Finally, we assign the newPq back to pq using std::move() to avoid copying.

The output of this code will be:

140 30 10

As you can see, the element 20 has been removed from the priority queue.

Keep in mind that this approach has a time complexity of O(n log n), where n is the number of elements in the priority queue, as we need to rebuild the heap for the new priority queue. If you need to perform frequent removals of specific elements, you might consider using a different data structure or implementing a custom priority queue that supports this operation more efficiently.