具有 O(log n) 删除任意节点的优先级队列（或最小堆）
Priority queue (or min-heap) with O(log n) deletion of arbitrary node
我有一堆项目存储在最小堆中（通过 PriorityQueue），我需要有效地删除任意项目。我知道在标准的最小堆实现中，删除任意元素（假定您知道该元素在堆中的位置）需要 O(log n) 时间，而 finding位置是 O(n)。所以，基本上，我需要保留一个单独的数据结构来保存每个项目在堆中的位置。
我或多或少知道如何从头开始实现它，但我想知道是否有一种聪明的方法可以 utilize/subclass PriorityQueue（具有其他有用的功能）完成这个。
澄清一下，我需要 PQ/Min-Heap 提供的 O(1) 最小窥视时间。
您是否考虑过使用 TreeMap. It is like a PriorityQueue with Map 之类的功能。
TreeMap 不支持O(1) 的删除操作，但是它执行O(logN) 的删除操作。比 PriorityQueue 的 O(N) 支持要好得多。它还 returns 集合的头部（最小或最大元素取决于比较器，就像 PriorityQueue 一样）。除此之外，它还 returns 集合的尾部（ max 或 min ）。 PriorityQueue 不支持尾部功能，因此您有时最终会保留两个队列来跟踪头部和尾部。
- 头元素 -> TreeMap#firstKey
- 尾元素 -> TreeMap#lastKey
定义
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.
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)| - |
+----------------+-----------------+----------------------------------------------+
我还需要快速（log N）堆删除来处理超时。 Java 的标准 PriorityQueue 在队列中有数万个必须经常删除的元素时非常低效。
所以这是我创建的堆实现：fast-delete-heap
所以基本上它维护了一个额外的散列映射，带有元素到堆的索引，允许快速 O(log N) 删除。不过，它的插入速度较慢。
我有一堆项目存储在最小堆中（通过 PriorityQueue），我需要有效地删除任意项目。我知道在标准的最小堆实现中，删除任意元素（假定您知道该元素在堆中的位置）需要 O(log n) 时间，而 finding位置是 O(n)。所以，基本上，我需要保留一个单独的数据结构来保存每个项目在堆中的位置。
我或多或少知道如何从头开始实现它，但我想知道是否有一种聪明的方法可以 utilize/subclass PriorityQueue（具有其他有用的功能）完成这个。
澄清一下，我需要 PQ/Min-Heap 提供的 O(1) 最小窥视时间。
您是否考虑过使用 TreeMap. It is like a PriorityQueue with Map 之类的功能。
TreeMap 不支持O(1) 的删除操作，但是它执行O(logN) 的删除操作。比 PriorityQueue 的 O(N) 支持要好得多。它还 returns 集合的头部（最小或最大元素取决于比较器，就像 PriorityQueue 一样）。除此之外，它还 returns 集合的尾部（ max 或 min ）。 PriorityQueue 不支持尾部功能，因此您有时最终会保留两个队列来跟踪头部和尾部。
- 头元素 -> TreeMap#firstKey
- 尾元素 -> TreeMap#lastKey
定义
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.
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)| - |
+----------------+-----------------+----------------------------------------------+
我还需要快速（log N）堆删除来处理超时。 Java 的标准 PriorityQueue 在队列中有数万个必须经常删除的元素时非常低效。
所以这是我创建的堆实现：fast-delete-heap
所以基本上它维护了一个额外的散列映射，带有元素到堆的索引，允许快速 O(log N) 删除。不过，它的插入速度较慢。