NoN*_*eY0 8 algorithm data-structures
设计一个支持n元素集上的以下操作的数据结构:
O(lg n)O(1)时间.请注意,删除max占用O(lg n)传统堆.我的方法:
我决定保留一个单独的数组,它将跟踪将超越根的潜在后继者(这是最大堆中的最大值); 一旦删除.因此,如果你删除max,O(1)我将在我的数组中查找下一个合适的后继者(我假设我将智能地设置).
有人有更好的方法吗？尽量坚持使用堆.这不是一个家庭工作的问题,我正在准备面试,而且它来自Skiena的书.
您的要求非常具体——您只对这两个操作感兴趣：插入O (lg n ) 和 deleteMin O (1)。
没有一个已知的堆结构满足您的特定约束。相反，最好的结构（尽管理论上——有些人称之为银河结构）是Brodal Queue，它在O (1) 最坏情况下执行所有堆操作，除了 deleteMin 仍然需要O (lg n ) 最坏情况-案例时间。所有其他已知的结构也好不到哪里去。
由于您只对这两个操作感兴趣，因此您可能能够摆脱只处理这两个操作的自定义结构，因为您不必担心减少键，合并等更多一般堆结构不用担心。
保持双重结构DL，包含：
此外，在L 中的每个条目与其对应的D或T 中的条目之间保持链接，反之亦然。此外，您需要为D 的每个条目维护一个位，指示它是否已在L 中被删除。为了以后做之间的质量同步d和大号，你可能还需要跟踪缺失的数量，d，从大号自上次同步。您可以在以下不变量之后进行同步：
被侵犯。这样同步时间在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 所指出的，这些成本已摊销。我已经更新了描述以强调这一事实并为清晰起见进行了修改。也许，通过一些技巧可以消除摊销，但在这种情况下，我们最终会得到另一个银河结构。