Remove Element from Priority Queue in C++

In C++, a priority_queue is a container adapter that provides a way to access its elements in order of priority. The underlying implementation of a priority_queue is typically a binary heap.

Priority queue does not directly support the operation of deleting a specified element, but it can be achieved by using some techniques.

One approach is to mark the elements to be deleted as invalid, and then ignore these invalid elements when accessing them. This method is suitable for cases where the values of the elements are not unique.

Another approach is to create a new priority queue and then insert all elements except the one to be removed into the new queue. This method is suitable for cases where the values of the elements may be duplicates.

Here is an example code demonstrating how to remove a specific element.

#include <iostream>
#include <queue>
using namespace std;

// 删除指定元素的函数
template<typename T>
void removeElement(priority_queue<T>& pq, T element) {
    priority_queue<T> newPq; // 创建一个新的优先队列

    // 将要删除的元素之外的所有元素插入到新队列中
    while (!pq.empty()) {
        T value = pq.top();
        pq.pop();
        if (value != element) {
            newPq.push(value);
        }
    }

    pq = newPq; // 将新队列赋值给原队列
}

int main() {
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);
    pq.push(4);

    removeElement(pq, 2); // 删除元素2

    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出：4 3 1
        pq.pop();
    }

    return 0;
}

In the example code above, we have defined a removeElement function to delete a specified element. This is done by creating a new priority queue, inserting all elements except the one to be deleted into the new queue. Then, assigning the new queue back to the original queue achieves the goal of removing the specified element.

Please note that this method is only applicable to element types that support assignment operations. If the element type does not support assignment operations, consider using other containers such as std::vector to achieve the functionality of deleting specified elements.