8

许多快速优先级队列（例如斐波那契堆和配对堆）支持减少键操作，该操作采用已存储在优先级队列中的元素并有效地降低其优先级。在斐波那契和配对堆的情况下，减少键的执行速度比从优先级队列中删除元素并稍后重新插入它要快。

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

谢谢！

4

2 回答 2

1

想象以下场景：

你开始 N 个元素。现在，

  1. 您创建一个大小为 N 的“有序字典”，其中包含大于任何元素的某个值 X 的 N 个副本。
  2. 然后在每个 X 上调用 reduction-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 或跳过列表）。
于 2013-04-22T10:55:44.070 回答
0

排序数组或排序链表支持O(1)减少或增加键（假设没有/最少重复，请参阅第 4 段）。这是因为，如果您考虑一下，您最多需要交换 2 个元素来进行减键或增键操作。

不是实践中最好的数据结构（尽管它们有自己的位置），但仍然是一个答案。

唯一的限制是您需要一个指向该节点的指针才能开始，因为它已经O(log n)分别O(n)用于查找该节点。

如果有重复，则移动可能O(n)对两者都采取最坏的情况（如果大多数值相同），这是非常糟糕的。但是，对于链表，应该可以O(1)通过具有某种链表的链表来获得，其中大链表中的每个节点代表一个特定的值，并且从那里的每个链表代表所有节点等于那个值。

我关于为什么 BBST 或跳过列表不起作用的原始答案：

（没有删除，因为浪费似乎很可惜）

对于 BBST 或跳过列表来说，最坏的情况小于O(log n)移动单个元素是不可能的，尽管据我所知，它至少与 re-insert 一样有效。平均情况可能小于O(log n).

我们正在寻找它 -查找只是为了找到您想要移动的元素的位置，O(log n)显然您需要这样做。

如果您出于某种奇怪的原因已经拥有该职位：

为什么最坏情况的移动不能少于O(log n)BST：考虑当试图移动根并且下一个元素位于树的高度时（例如，右孩子有一个左孩子，一个左孩子有一个左孩子左孩子...下降到树的高度）。你需要O(log n)找到它。

为什么最坏情况下的移动不能少于O(log n)跳过列表：考虑一个存在于O(log n)列表中的项目，然后是一个存在于O(log n)这些列表中的项目（如果可能的话，从图片中可以看出，我对跳过列表有点基本）。您显然需要交换O(log n)列表中的适用项目。

如果您已经拥有该职位，则可能存在一个有效的有序结构，但可能不适用于任何基于树的结构（因为上面提出的论点），据我所知，大多数有效的有序结构结构。

于 2013-01-05T23:22:15.357 回答