java - 自适应优先级队列中位置的使用

Question

当我们必须将 Entry 引用传递给函数remove(k)、replaceKey(k) 时，Adaptable 优先级队列(基于列表的键堆)中的 Position 有何用途。即，如果我对队列中的某个条目有一些引用“ref”，那么我可以简单地调用remove(ref)和replaceKey(ref)，但这仍然需要O(1)时间。为什么我需要为此提供特殊职位？

Answer 1

1. 将堆实现为链表根本没有任何意义。堆本质上是几乎完整的二叉树。您可以将堆存储在数组中，因为计算节点子节点的数组索引很容易:位置 i 处的节点的子节点位于位置 2i + 1 和 2i+2 处。查找数组的第 i 个元素比查找链表的第 i 个元素要高效得多。

2. 对于自适应优先级队列，数组(堆)是对位置实例的引用序列，每个实例都存储一个键、值以及数组中项目的当前索引。用户将获得对每个插入元素的 Position 实例的引用。当我们在堆上执行优先级队列操作并且项目被重新定位时在我们的结构中，我们重新定位数组中的位置实例，并且我们更新每个位置的第三个字段以反射(reflect)其在数组中的新索引，更新将花费 O(log(n)) 时间复杂度。