我最近阅读了 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 )
这篇论文谈了很多关于“腐败”的话题。什么是腐败，元素是如何腐败的，它对你有什么帮助？
我花了很多时间阅读论文和谷歌搜索，但这仍然没有意义。
在大多数关于优先级队列的研究论文中，队列中的每个元素都有一个关联的编号，称为优先级，该编号在插入元素时设置。然后元素按优先级递增的顺序出列。如今，大多数支持优先级队列的编程语言实际上并不使用显式优先级，而是依靠比较函数来对元素进行排名，但软堆使用“关联数字优先级”模型。
因为优先级队列按优先级递增的顺序出列元素，它们可用于对一系列值进行排序 - 首先将每个元素插入优先级队列，其优先级等于其在序列中的排名，然后从优先级队列中出列所有元素. 这会将元素按排序顺序拉出。
但是，优先级队列和排序之间的这种联系是有代价的。比较排序算法有已知的下限（没有比较排序算法的运行时间可以优于 O(n log 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 次删除的运行时间可以是 O(n) - 比 O(n log n) 快。最初，软堆被用作构建最小生成树的快速算法的构建块。它们还用于线性时间选择的新算法，这是自著名的中位数算法以来第一个在线性时间内运行的确定性算法。在这两种情况下，软堆都用于“近似地”对输入元素进行排序，从而让算法获得排序序列的粗略近似值，此时算法会执行一些额外的逻辑来纠正缺少的完美。
总结一下：
希望这可以帮助！
答案在第二页：
并观察到，如果每个键都因将其值提高到 ` 而被破坏，那么键集的熵将为零，我们可以在恒定时间内轻松执行所有操作。有趣的是，软堆表明熵不需要降到零，复杂度就会变得恒定。”
这是弄巧成拙的数据结构吗？