algorithm - 删除 O(1) 中的最大值并插入 O(logn)

Question

设计一个数据结构，支持对 n 元素集进行以下操作:

及时插入 O(lg n)

删除 O(1) 中的最大值时间。请注意，删除最大需要 O(lg n)在常规堆中。

我的做法:

我决定保留一个单独的数组，它将跟踪将超过根的潜在后继者(这是最大堆中的最大值)；一旦被删除。所以如果你删除最大值，在 O(1)有时间我会查看我的数组以找到下一个合适的继任者(我认为我已经聪明地设置了)。

有人有更好的方法吗？尽量坚持使用堆。这不是家庭作业问题，我正在准备面试，它来自 Skiena 的书。

Answer 1

您的要求非常具体——您只对这两个操作感兴趣:插入 O(lg n) 和 deleteMin O(1)。

没有一个已知的 heap structures满足您的特定限制。相反，最好的结构(尽管理论上是 Galactic structures，有些人会这样称呼它们)是 Brodal Queue ，它在 O(1) 最坏情况下执行所有堆操作，除了 deleteMin 仍然需要 O(lg n) 最坏情况时间。所有其他已知的结构也好不到哪里去。

由于您只对这两个操作感兴趣，因此您可能能够摆脱只处理这两个操作的自定义结构，因为您不必担心减少键，合并等更多一般堆结构不用担心。

保持双重结构，DL，包含:

已排序 dynamic array , D, 从中你可以通过二分搜索在 O(lg n) 时间内找到。

排序链表 L，从中您可以在 O(1) 时间内执行 deleteMin，并在 O(1) 最坏情况下给定后继(或前驱)引用进行插入。

最近插入到 L 但尚未与 D 同步的元素的排序列表 T。

此外，在 L 中的每个条目与其对应的 D 或 T 中的条目之间保持链接，反之亦然。此外，您需要为 D 的每个条目维护一个位，指示它是否已在 L 中被删除。为了稍后在 D 和 L 之间进行大规模同步，您可能还需要跟踪自上次同步以来从 L 中删除的次数 d。您可以在以下不变量之后进行同步:

不变量 1: d + |T| < n

被侵犯。这样同步时间在 n 中保持线性并且您始终可以保证 |T|和 d 在可控范围内。

因此，要将新元素 e 插入 DL，首先在 D 中为其后继(前任)执行 find(e) 并在 T 中再次搜索其后继并获取较大后继(较小前任)的引用并使用它插入 L 并将 e 添加到 T 并维护引用。插入 e 后，我们检查是否违反了不变量 1。如果是这样，我们触发同步。

同步本质上是合并 T 和 D 的内容，同时将标记为已删除的元素移除到新的 D 结构中。这可以在 |T| 的时间线性内完成+ |D| = O(n)。在另一个线性时间内，可以更新 L 和 D 之间的引用。这种大规模同步的成本可以通过插入和删除来分配(摊销)。因此，这些成本只是摊销成本。

要执行deleteMin，您只需删除L 的头部并使用其到D 的反向链接将其在D 中的相应条目标记为已删除并递增d。

观察 1 :请注意，deleteMin 将始终删除最小元素，因为 L 始终是最新的。

观察 2 :D 并不总是与 L 同步。它可能有一些删除的元素(如此标记)和一些插入的元素只能在 T 中找到。

通过观察 2，我们需要在某个时刻安排 D 与 L 的同步，以维持 O(lg n) 查找和插入成本。每当违反不变量 1 时都会执行此操作。

我稍微掩盖了一个讨厌的问题如下:如何在对数时间内插入 T，同时仍然能够在同步期间进行线性扫描。只有某种平衡的树才能实现这一点。我曾想过将 T 的大小限制为对数大小的想法，但是当完成足够数量的插入以触发同步时，这会增加同步的摊销成本。似乎一种线程平衡树甚至跳过列表应该在这里有所帮助。

随意批评并提出改进建议，因为我还没有证明或实现这里的所有断言。

更新 :正如@delnan 所指出的，这些成本已摊销。我已经更新了描述以强调这一事实并为清晰起见进行了修改。也许，通过一些技巧可以消除摊销，但在这种情况下，我们最终会得到另一个银河结构。