如何从priority_queue中删除不在顶部的元素？

Question

在我的程序中，我需要从不在顶部的优先级队列中删除一个元素。可以这样做吗？如果没有，请提出一种方法，除了创建自己的堆。

原文由 ishan3243 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

处理priority_queue STL的删除的一个巧妙的小技巧 - 使用另一个priority_queue，例如 del_pq 。继续向其中插入所有删除值。当您从原始优先级队列中弹出值时，请检查 del_pq 的顶部，看看我们是否要删除它。如果匹配，则从原始priority_queue 中删除该值。

此方法实现了一种延迟删除原始优先级队列中的值的方法。可以占用两倍内存，但平均删除和插入仍然存在 O(logN) 。

原文由 Rishabh Jain 发布，翻译遵循 CC BY-SA 4.0 许可协议