在O(1)时间内删除最大值并在O(logn)时间内插入。

Question

在O(1)时间内删除最大值并在O(logn)时间内插入。

algorithmdata-structures

9

设计一种数据结构，支持在一个n元素集合上进行以下操作：

时间复杂度为O(lg n)的插入操作
时间复杂度为O(1)的删除最大值操作。请注意，传统堆的删除最大值需要O(lg n)的时间。

我的方法是：我会保留一个单独的数组，用于跟踪可能在删除根（即最大值）后接替其位置的潜在后继者。所以如果您删除最大值，我将在O(1)的时间内查找我的数组，以找到下一个合适的后继者（我假设我已经设置好了智能的后继者）。

有没有更好的方法？请尝试使用堆。这不是一道家庭作业题，我正在为面试做准备，这个问题来源于Skiena的书。

- NoNameY0

这真的可能吗？我不确定你是否可以每个元素在O(lg n)内构建数组。 - John Dvorak

4

斐波那契堆和跳跃表可以实现这个功能。我正在尝试想出一个更简单的解决方案，并将很快发布答案。 - Ivaylo Strandjev

那么，在O(1)中删除最大值是否包括任何必要的修复，以使结构保持其不变性？这是最坏情况还是平摊O(1)？如果是最坏情况，除了排序链表（显然在这里行不通）之外，还有哪些选项？ - Jon

这个插入是针对一个元素还是n个元素？也许是红黑树？- http://en.wikipedia.org/wiki/Red%E2%80%93black_tree - Kunukn

1

集合必须具备更多的操作，例如迭代或成员测试。否则，在这两种情况下都可以通过不执行任何操作来实现（O(1)）。 - Erik P.

显示剩余4条评论

3个回答

4

我建议你使用跳表，因为它是我所能想到的最容易实现支持所需操作的数据结构。斐波那契堆也可以完成工作，但它难度要大得多。

编辑：我收回对斐波那契堆的看法——它支持常数插入和O(log(n))删除最小值，这与你想要的相反。很抱歉。

- Ivaylo Strandjev

4

如果你想让事情变得非常复杂，还有Brodal队列，它是斐波那契堆的去摊存在版本。 - Antimony

1

请提供@Antimony的链接。如果它是以一个人的名字命名的，那一定很好。 - John Dvorak

如果您正在使用分摊复杂度，那么在常数插入和对数删除之间，以及常数删除和对数插入之间并没有真正的区别。 - Antimony

@RichardMckenna 我还在考虑一个更简单的解决方案。 - Ivaylo Strandjev

跳表是一个非常好的解决方案，而且实现起来并不比二叉堆更困难。 - Jim Mischel

显示剩余5条评论

0

最简单的解决方案是使用跳表（skiplist）维护始终排序的集合，插入时间为O(logn)，然后您可以在O(1)时间内删除最大或最小元素，因为它将是列表的头部或尾部。

- vladich

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rrufai · Accepted Answer

你的要求非常具体——你只关心这两个操作：插入O(lg n)和删除最小值O(1)。

目前已知的堆结构都无法满足你的要求。相反，最好的结构（尽管从理论上来说——有些人称之为星际结构）是Brodal队列，它在最坏情况下可以完成所有堆操作，时间复杂度为O(1)，除了删除最小值仍然需要O(lg n)的最坏情况时间。所有其他已知的结构都不如它。

由于你只关心这两个操作，你可能可以使用一个自定义结构来处理它们，因为你不必担心更一般的堆结构需要担心的减少键、合并等问题。

维护一个双重结构DL，包含：

已排序的动态数组 D，可以通过二分查找在O(lg n)时间内进行查找。
已排序的链表L，可以在O(1)时间内执行deleteMin操作，并在O(1)最坏情况下插入给定后继（或前驱）引用。
元素最近插入到L中的已排序列表T，但尚未与D同步。

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

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

被违反了。这样同步时间就保持在n的线性范围内，您可以始终保证|T|和d处于可管理的限制范围内。

因此，要将新元素e插入到DL中，您首先在D中进行查找(e)，以获取其后继(前驱)，并在T中进行另一个搜索以获取其后继，并获取更大的后继(更小的前驱)的引用，然后使用它来对L进行插入，并将e添加到T中并维护引用。插入e后，我们检查是否违反了不变量1。如果是，则触发同步。

一次同步实际上将 T 和 D 的内容合并在一起，同时将标记为已删除的元素移动到新的 D 结构中。这可以在线性时间内完成，即| T | + | D | = O（n）。在另一个线性时间内，可以更新 L 和 D 之间的引用。这种大规模同步的成本可以分摊（平摊）到插入和删除中。因此，这些成本只是摊销成本。
要执行deleteMin，您只需删除 L 的头部，并使用其向后链接到 D 来将其对应条目标记为删除并增加 d 。观察1 ：请注意， deleteMin 将始终删除最小元素，因为 L 始终是最新的。观察2 ： D 与 L 不总是同步的。它可能具有一些已删除的元素（因此标记），以及仅在 T 中找到的一些已插入元素。
根据观察2，我们需要在某个时刻安排D与L同步，以保持O(lg n)的查找和插入成本。只有当不变量1被违反时才会执行此操作。
我稍微忽略了一个麻烦的问题：如何在对sync进行线性扫描的同时以对数时间插入T。只有某种平衡树才能实现这一点。我曾经尝试过将T的大小限制为对数大小，但是这样做会增加同步的摊销成本，因为插入足够多的数字会触发同步。似乎一种线索平衡树甚至是跳表应该可以帮助解决这个问题。
欢迎批评和提出改进意见，因为我没有证明或实现这里的所有断言。
更新：正如@delnan指出的那样，这些成本是摊销的。我已经更新了描述以突出这一事实并进行了修订以提高清晰度。也许通过一些诡计可以消除摊销，但在这种情况下，我们将得到另一个银河系结构。