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

Question

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

标签： javadata-structures

Answer 1

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

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