优先级队列以从集合中检索最大或最小元素而闻名。优先级队列上的两个常见操作是 Insert 和 DeleteMin/DeleteMax。我们有支持 Delete(x( 的优先级队列吗？Delete(x( 的含义是从优先级队列中删除项目 x。
执行此操作的天真方法是找到项目 x 并将其删除，但这需要线性时间。我正在寻找一些更好的算法。
某些类型的优先级队列确实支持此操作。通常，您可以通过让 delete(x( 操作接受 x 作为数据结构内的指针来指示应删除哪个元素来执行此操作。例如，在二项式堆或斐波那契堆中，每个元素都存储为森林中的一个节点，insert(x( 操作可能会返回指向保存元素 x 的节点的指针，然后 delete(x( 可以按照提供的指针快速找到要删除的元素。
在大多数以这种方式支持 delete(x( 的优先级队列(斐波那契堆、二项式堆、配对堆等(中，delete(x( 的复杂度与 delete-min 的复杂度相同，但这取决于数据结构的特定实现。
希望这有帮助！
如果优先级队列库不支持Delete(x)函数，我会使用一种作弊方式。
我将使用 2 个优先级队列，ORI 和 DELETED . ORI将是我原来的优先级队列，DELETED充当一个池来标记哪些元素被删除。
要添加元素，只需将其添加到 ORI 中即可。要删除元素，只需将其添加到 DELETED .
当您查询优先级队列的顶部(例如最小值/最大值(时，魔术就来了：
1(当ORI的顶部等于DELETED时，删除两个优先级队列的顶部(使用DeleteMin/DeleteMax(
2(一旦两个优先级队列的顶部不相等，ORI的顶部将是您要查找的实际"顶部"。
这在某种程度上延迟了"删除"，直到要删除的元素位于优先级队列的顶部。这是有效的，因为如果标记为要删除的元素不是优先级队列的顶部，则优先级队列的顶部不会更改。
然而，这种"作弊"的缺点是需要更多的内存来存储标记为"删除"的元素。
删除函数的复杂性最终被Armotized O(log N(
编辑：这样，您就不必实现自己的数据结构:P我一直在使用这种技术在C++使用STL优先级队列的编程竞赛中使用这种技术。
任何平衡的二叉树结构都可以在插入和删除下存储排序序列，而不仅仅是最小元素，并且获得与二进制堆类似的渐近时间界限。