一个支持减少键的有序字典？

Question

许多快速优先级队列(例如Fibonacci堆和配对堆)支持减少键操作,该操作采用已存储在优先级队列中的元素并有效地降低其优先级.在Fibonacci和配对堆的情况下,reduce-key的执行速度比从优先级队列中删除元素并稍后重新插入要快.

我想知道在有序字典结构(二叉搜索树,跳过列表等)上是否可以支持类似的操作.具体来说,假设我有一个有序字典,并希望将某个键/值对的键更改为不同的键.是否可以在有序字典的任何标准表示中按时间O(1)或O(log log n)执行此操作？我很好奇,因为有了平衡的BST,这可以在O(log n)时间内通过删除元素并重新插入来完成,但似乎可能有更快的方法来做到这一点.

谢谢!

Answer 1

想象一下以下场景：

你开始 N 个元素。现在，

1. 您创建一个大小为 N 的“有序字典”，其中包含大于任何元素的某个值 X 的 N 个副本。
2. 然后，您对每个 X 调用decrease-key，将其更改为 N 个实数元素之一。
3. 遍历字典，按顺序读出元素。

在大多数有序字典的实现中，步骤 1 和 3 都需要 O(N) 时间。如果减少键需要 O(1) 或 O(log log N) 时间，则步骤 2 需要 O(N) 或 O(N log log N) 时间。这意味着您可以用 O(N) 或 O(N log log N) 时间进行排序。

根据基于比较的排序的 O(N log N) 下限，这意味着您不能在 O(1) 或 O(N log log N) 时间内执行减少键操作，除非

• 您的有序字典不是基于比较（通常只有当您了解元素的特殊情况时才会发生这种情况，例如它们都在 1-100 范围内），或者
• 您的有序字典不支持 O(N) 时间内的步骤 1 和 3（这将排除所有常见的嫌疑人，例如 BST 或跳过列表）。