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

Question

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

我或多或少知道如何从头开始实现这一点，但我想知道是否有一种巧妙的方法来利用/子类PriorityQueue（具有其他有用的功能）来实现这一点。

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

Answer 1

您是否考虑过使用TreeMap。它就像具有类似Map功能的PriorityQueue。

\n

TreeMap不支持O(1)的删除操作，但是它执行删除操作的时间为O(logN)。比 PriorityQueue 的 O(N) 支持好得多。它还返回集合的头部（最小或最大元素取决于比较器，就像 PriorityQueue 一样）。除此之外，它还返回集合的尾部（ max 或 min ）。PriorityQueue 不支持尾部功能，因此有时您最终会保留两个队列来跟踪头部和尾部。

\n

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

\n

定义

\n

\n
• 树形图
\n

\n

\n

基于红黑树的 NavigableMap 实现。\n地图根据其键的自然顺序排序，\n也不是通过地图创建时提供的比较器排序，具体取决于\n使用哪个构造函数。此实现提供有保证的\nlog(n ) containsKey、get、put 和 remove 操作的时间成本。\n算法改编自 Cormen、Leiserson 和 Rivest\n算法简介中的算法。

\n

\n

\n
• 红黑树
\n

\n

\n

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

\n

\n

参考《算法导论》中的红黑树算法

\n

运行时间：

\n

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

\n