data-structures - 软堆 : what is corruption and why is it useful?

Question

我最近阅读了 Bernard Chazelle 的论文“The Soft Heap, An Approximate Priority Queue with Optimal Error Rate by Bernard Chazelle”(http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf)

该报大量谈论“腐败”。什么是腐败，元素是如何被腐 eclipse 的，它对你有什么帮助？

我花了很多时间阅读论文和谷歌搜索，但这仍然没有意义。

Answer 1

在大多数关于优先级队列的研究论文中，队列中的每个元素都有一个相关的编号，称为优先级，该编号在插入元素时设置。然后元素按优先级递增的顺序出列。现在大多数支持优先级队列的编程语言实际上并不使用显式优先级，而是依靠比较函数来对元素进行排序，但软堆使用“关联数字优先级”模型。

由于优先级队列按优先级递增的顺序将元素出列，因此它们可用于对值序列进行排序 - 首先将优先级等于其在序列中的排名的每个元素插入优先级队列，然后将所有元素从优先级队列中出队.这将按排序顺序拉出元素。

不过，优先级队列和排序之间的这种连接是有代价的。比较排序算法有已知的下限(没有比较排序算法的运行时间可以优于 O(n log n))。因此，任何基于比较的优先级队列的运行时间都有一个下限。具体来说，n 个入队和 n 个出队的总成本必须不高于 O(n log n)。大多数情况下，这很好，但在某些情况下，这还不够快。

只要可以使用优先级队列对输入序列进行排序，n 个入队和 n 个出队的运行时间永远不会超过 O(n log n)。但是如果优先级队列不对输入进行排序呢？将其发挥到极致——如果优先级队列以完全任意的顺序交回元素，那么就有可能在 O(n) 时间内实现 n 个入队和 n 个出队——例如，只需使用堆栈或队列。

直观地说，您可以将软堆视为“始终排序”和“对顺序没有任何保证”这两个极端之间的桥梁。每个排序堆都在某个称为“损坏参数”的量 ε 上进行参数化，该参数决定了从软堆中出来的值与排序的接近程度。具体来说，随着 ε 越接近 0，输出将逐渐变得更加有序，而随着 ε 越接近 1，输出将逐渐变得更加随意。适本地，软堆操作的运行时间被确定为 O(log ε-1) 的函数，因此操作的运行时间随着 ε 的增加而变得越来越便宜(因此，输出变得更少排序)并且随着 ε 下降，操作变得更加昂贵(在这种情况下，输出变得越来越排序)。

软堆使用新的“损坏”概念精确量化输出的未排序程度。在普通的优先级队列中，一旦插入元素/优先级对，元素的优先级就永远不会改变。在软堆中，当元素位于软堆内时，与优先级关联的元素可能会损坏。当一个元素的优先级被破坏时，它的优先级会上升一些。 (由于软堆按优先级递增的顺序将元素出列，元素的优先级递增意味着它将比正常情况更晚从队列中出来)。换句话说，损坏将导致元素不按排序顺序出现，因为元素出列时的优先级不一定与入队时相同。

ε 的选择会调整多少不同元素的优先级会被破坏。 ε 小，优先级损坏的元素越少，ε 大时，优先级损坏的元素越多。

现在，对于你的具体问题——元素的优先级是如何被破坏的，这对你有什么帮助？你的第一个问题很好 - 数据结构如何决定何时破坏优先级？有两种查看方式。首先，您可以将软堆视为一种数据结构，您可以在其中预先指定可接受的损坏程度(即 ε 参数)，然后数据结构在内部决定何时以及如何损坏优先级，只要它不超过某个总腐败水平。如果让数据结构做出这样的决定看起来很奇怪，请考虑使用布隆过滤器或跳过列表之类的东西，其中确实存在内部随机选择，可以影响数据结构的可观察行为。事实证明，软堆通常不是使用随机性实现的(这是一个令人印象深刻的特性!)，但这在这里并不是特别相关。

在内部，软堆的两个已知实现(一个来自 Chazelle 的原始论文，后来使用二叉树进行清理)使用称为拼车的技术实现损坏，其中元素组合在一起并共享一个共同的优先级。损坏的发生是因为每个组中所有元素的原始优先级都被忘记了，而是使用了新的优先级。元素如何分组的实际细节非常复杂，并不值得研究，因此最好将其保留为“数据结构选择随心所欲地破坏，只要它不破坏更多元素比您在选择 ε 时指定的要多。”

接下来，为什么这很有用？在实践中，事实并非如此。软堆几乎完全具有理论意义。理论上它很好的原因是软堆中 n 次插入和 n 次删除的运行时间可以是 O(n) - 比 O(n log n) 快 - 如果 ε 选择正确。最初，软堆被用作构建最小生成树的快速算法中的构建块。它们还用于线性时间选择的新算法，这是自著名的中值中值算法以来第一个在线性时间中运行的此类确定性算法。在这两种情况下，软堆都用于对输入元素进行“近似”排序，使算法可以粗略地近似排序序列，此时算法会执行一些额外的逻辑来纠正缺少的完美。您几乎肯定不会在实践中看到使用软堆，但是如果您最终找到了一个案例，请发表评论并告诉我!

总结一下:

破坏优先级是在完美排序(精确但缓慢)和任意排序(不精确但非常快)之间进行权衡的一种方式。参数 ε 确定损坏量在频谱上的位置。

腐败通过改变软堆中现有元素的优先级来起作用，特别是通过提高某些元素的优先级。低损坏对应于近似排序的序列，而高损坏对应于更任意的序列。

执行损坏的方式是特定于数据结构的并且非常难以理解。最好将软堆视为在需要时执行损坏，但绝不能超出选择 ε 所施加的限制。

损坏在排序太慢的理论设置中很有帮助，但大致正确排序的序列对于实际目的来说已经足够了。在实践中不太可能有用。

希望这有帮助!