具有O(log n)删除任意节点的优先队列（或最小堆）

Question

我有一堆项目存储在一个小根堆中（通过PriorityQueue实现），我需要高效地删除任意项目。我知道在标准的小根堆实现中，删除任意元素（假设你知道该元素在堆中的位置）需要O(log n)时间，而查找位置需要O(n)时间。所以，基本上，我需要保持一个单独的数据结构来保存每个项目在堆中的位置。

我大概知道如何从头开始实现这个功能，但我想知道是否有一种聪明的方法利用/子类化PriorityQueue（具有其他有用的特性）来实现这一点。

为了澄清，我需要PQ /小根堆提供的O(1)peek-min。

- DanM

---

使用TreeSet代替PriorityQueue。 - ead

我不知道是否有这样的可能性，如果真的有的话，我会感到惊讶，但谁知道呢... - ead

remove-min的时间复杂度不是O(1)。peek操作的时间复杂度���O(1)，但是remove-min的时间复杂度为O(log n)。如果你想要任意节点的O(log n)删除，你需要在每次节点在PQ数组中移动时更新相应的数据结构。我没看到Java PQ实现有一个可以使用的通知。最好的方法可能是获取Java PQ源代码并将其修改以满足你的需求。或者使用像Paring heap这样的数据结构，它可以使这种操作变得相对简单。 - Jim Mischel

@JimMischel 噢，是的，O(1) 的 peek，O(log n) 的 poll。那是我犯了个脑抽。 - DanM

平衡二叉搜索树，加上对最小值的引用，能够实现这个功能吗？每次插入时，您都知道它是否比最小值小，并且可以更新；每次删除最小值时，您可以在O(log n)中找到新的最小值，这不会改变删除的复杂度。看起来应该可以工作。同时，您可以在O(log n)中查找。公平地说，在平衡良好的BST中已经有了对最小值的引用，如果对平衡有足够严格的要求，删除最小值实际上应该是O(1)，我认为，在此期间您应该找到新的最小值。不确定，字数已用完。 - moreON

Answer 1

你有没有想过使用TreeMap？它类似于具有PriorityQueue和Map功能的组合。

TreeMap不支持O(1)的删除操作，但它可以在O(logN)的时间内完成删除操作。这比PriorityQueue支持的O(N)更好。它还返回集合的头部元素（根据比较器来看是最小或最大元素，就像PriorityQueue一样）。除此之外，它还返回集合的尾部元素（最大或最小）。PriorityQueue不支持尾部功能，因此有时您需要保留两个队列来跟踪头部和尾部。

• 头部元素 -> TreeMap#firstKey
• 尾部元素 -> TreeMap#lastKey

定义

• TreeMap

基于红黑树的NavigableMap实现。 该映射根据其键的自然排序或在创建映射时提供的比较器进行排序， 具体取决于使用哪个构造函数。该实现为包含键，获取值，插入和删除操作提供了有保障的log(n)时间复杂度。 算法是Cormen、Leiserson和Rivest的“Introduction to Algorithms”中适应的。

• 红黑树

红黑树是计算机科学中一种自平衡二叉搜索树。二叉树的每个节点都有一个额外的比特位， 并且该比特位通常被解释为节点的颜色（红色或黑色）。这些颜色位用于确保在插入和删除期间树保持大致平衡。

介绍算法中红黑树算法的参考资料

运行时间：

+----------------+-----------------+----------------------------------------------+
|   Operation    |     TreeMap     |                PriorityQueue                 |
+----------------+-----------------+----------------------------------------------+
| Insert(Object) | O(logN)[put]    | O(logN)[add]                                 |
| Get(Object)    | O(logN)[get]    | O(N)+ O(N)+O(logN) [contains + remove + add] |
| Delete(Object) | O(logN)[remove] | O(N)[remove]                                 |
| Head           |O(logN)[firstKey]| O(1)(peek)                                   |
| Tail           | O(logN)(lastKey)| -                                            |
+----------------+-----------------+----------------------------------------------+

- tactition09

Answer 2

我也需要快速(log N)的堆删除来处理超时。当你有数万个要经常删除的元素时，Java的标准PriorityQueue效率相当低。

所以这里是一个我创建的堆实现: fast-delete-heap

基本上它维护了一个额外的元素到堆索引的哈希映射，允许快速的O(log N)删除。然而插入速度会慢一些。

- waypoint100