9

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

  1. 及时插入O(lg n)
  2. 及时删除最大值O(1)。请注意，delete max 采用O(lg n)常规堆。

我的做法：

我决定我将保留一个单独的数组，它将跟踪将超过根的潜在继任者（这是最大堆中的最大值）；一旦被删除。因此，如果您删除最大值，O(1)我会及时查看我的数组以找到下一个合适的继任者（我假设我将智能设置）。

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

4

3 回答 3

5

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

没有一个已知的堆结构满足您的特定约束。相反，最好的结构（尽管理论上——有些人称之为银河结构）是Brodal Queue ，它在O (1) 最坏情况下执行所有堆操作，但 deleteMin 仍然需要O (lg n ) 最坏情况-案例时间。所有其他已知结构也好不到哪里去。

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

维护双重结构DL，其中包含：

  1. 已排序的动态数组D，您可以通过二分搜索在O (lg n ) 时间内从中进行查找。
  2. 排序链表L，您可以在O (1) 时间内执行 deleteMin ，并在O (1) 最坏情况下执行插入给定后继（或前任）引用。
  3. 最近插入到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 所指出的，这些成本是摊销的。我更新了描述以突出这一事实，并为清楚起见进行了修订。也许，通过一些技巧可以消除摊销，但在这种情况下，我们最终会得到另一个银河结构。

于 2013-03-05T17:38:03.107 回答
4

我建议您使用跳过列表，因为它是我能想到的最容易实现的数据结构，它支持具有所需复杂性的操作。斐波那契堆也可以完成这项工作，但实施起来要困难得多。

编辑：我收回我对斐波那契堆的承诺——它支持常量 insert 和O(log(n))delete_min，这与你想要的相反。对此感到抱歉。

于 2013-03-05T13:32:00.440 回答
0

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

于 2017-01-21T19:34:18.743 回答