我最近阅读了Bernard Chazelle的论文“Bernard Chazelle的软堆，具有最佳错误率的近似优先级队列”(http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf)
该论文谈论了很多有关“腐败”的问题。什么是腐败，元素如何腐败以及如何为您提供帮助？
我花了很多时间通读论文和谷歌搜索，但这仍然没有意义。
最佳答案
在有关优先级队列的大多数研究论文中，队列中的每个元素都有一个称为优先级的关联编号，该编号是在插入元素时设置的。然后按优先级从高到低的顺序将元素出队。如今，大多数支持优先级队列的编程语言实际上并不使用显式优先级，而是依靠比较功能对元素进行排名，但是软堆使用“关联的数字优先级”模型。
由于优先级队列按优先级从高到低的顺序使元素出队，因此可以使用它们对值序列进行排序-首先将每个元素插入优先级队列，优先级等于其在该序列中的排名，然后将所有元素从优先级队列中出队。这将元素按排序顺序拉出。
但是，优先级队列和排序之间的这种连接是有代价的。比较排序算法的下限是已知的(比较排序算法的运行时不能比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)的函数，因此，随着ε的增加，操作的运行时变得越来越便宜(因此，输出得到的排序更少)，并且随着ε的下降，运算变得更加昂贵(在这种情况下，输出变得越来越多)。
软堆使用新的“腐败”概念精确地量化了输出将如何分类。在普通优先级队列中，一旦插入一个元素/优先级对，该元素的优先级就不会改变。在软堆中，当元素位于软堆内部时，与优先级关联的元素可能会损坏。当元素的优先级被破坏时，其优先级会增加一定量。 (由于软堆按优先级从高到低的顺序使元素出队，因此元素的优先级增加意味着它比正常情况下退出队列的时间更长)。换句话说，腐败将导致元素不按排序顺序出现，因为元素出队时的优先级不一定与元素出队时的优先级相同。
ε的选择可调整有多少个不同的元素可以破坏其优先级。如果ε较小，则优先级被破坏的元素较少，而ε较大，则优先级被破坏的元素更多。
现在，针对您的特定问题-元素的优先级如何被破坏，这对您有什么帮助？您的第一个问题是一个好问题-数据结构如何确定何时破坏优先级？有两种查看方式。首先，您可以将软堆视为一种数据结构，在该结构中您可以预先指定可接受的损坏程度(即ε参数)，然后该数据结构在内部确定何时以及如何损坏优先级(只要不破坏优先级)超过总的腐败水平。如果似乎很奇怪让数据结构做出这样的决定，请考虑使用Bloom过滤器或跳过列表之类的方法，其中确实存在内部随机选择，这些选择会影响数据结构的可观察到的行为。事实证明，软堆通常不使用随机性来实现(这是令人印象深刻的功能!)，但这在这里并不是特别重要。
在内部，软堆的两种已知实现(一种来自Chazelle原始论文的方法，后来使用二进制树进行清理)使用一种称为拼车的技术来实现损坏，该技术将元素分组在一起，并且所有元素都具有相同的优先级。发生损坏是因为忘记了每个组中所有元素的原始优先级，而是使用了新的优先级。元素如何分组的实际细节非常复杂，不值得研究，因此最好将其保留为“数据结构选择破坏它想要的，只要它不破坏更多元素比您选择ε时指定的值要大。”
接下来，这为什么有用？实际上，事实并非如此。软堆几乎只具有理论意义。从理论上讲很好的原因是，如果正确选择了ε，则从软堆中插入n次和从n次删除中删除n次的运行时间可以为O(n)-比O(n log n)快。最初，软堆在构建最小生成树的快速算法中用作构建块。它们还用于新的线性时间选择算法中，这是自著名的中间值中值算法以来第一个在线性时间中运行的确定性算法。在这两种情况下，都使用软堆对输入元素进行“近似”排序，以使算法可以粗略地近似排序序列，这时算法将执行一些额外的逻辑来纠正缺少的问题。完美。几乎可以肯定，您永远不会看到在实践中使用软堆，但是如果您最终找到了可以解决的情况，请发表评论，让我知道!
总结一下:
希望这可以帮助!
关于data-structures - 软堆: what is corruption and why is it useful?，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26126170/