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

Question

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

我或多或少知道如何从头开始实现它，但我想知道是否有一种聪明的方法来利用/子类化 PriorityQueue(它具有其他有用的功能)来完成这个。

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

Answer 1

您是否考虑过使用 TreeMap .它就像一个 PriorityQueue与 Map喜欢的功能。

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

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

定义

• TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

• Red-Black tree

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

Reference to Red-Black Trees algorithm in 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)| -                                            |
+----------------+-----------------+----------------------------------------------+