我最近阅读了Bernard Chazelle的论文“软堆：一种具有最优错误率的近似优先队列”。(http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf) 这篇论文经常提到“破坏”(corruption)。什么是“破坏”，元素如何受到破坏，以及它如何帮助您呢？我已经花了很多时间阅读这篇论文和搜索，但仍然不太理解。
2个回答
31
在大多数关于优先队列的研究论文中，队列中的每个元素在插入时都会被赋予一个称为优先级的相关数字。元素将按照递增的优先级顺序出队。现今大多数支持优先队列的编程语言实际上并不使用明确的优先级，而是依靠比较函数对元素进行排序。但软堆则采用“相关数字优先级”模型。
因为优先队列以优先级递增的顺序出队元素，所以它们可以用来对值序列进行排序 - 首先将每个元素插入到优先队列中，其优先级等于其在序列中的排名，然后从优先队列中将所有元素出队。这样就能以排序的方式取出元素。
然而，优先队列和排序之间的这种关联是有代价的。已知比较排序算法存在下限（没有比较排序算法的运行时间可以达到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的原始论文和后来基于二叉树进行的清理）使用称为拼车的技术对元素进行分组，并且所有元素共享一个公共优先级。由于每个组中所有元素的原始优先级被遗忘，并使用新的优先级，因此发生了破坏。元素分组的实际细节非常复杂，而且不值得深入研究，因此最好将其保留为“数据结构选择任意方式进行破坏，只要它不损坏超过您选择ε时指定的元素即可。”接下来，这有什么用处呢？ 实际上，几乎没有。 软堆heap几乎完全是理论性的。 之所以在理论上很好，是因为如果选择正确的ε，从软堆中进行n次插入和n次删除的运行时间可以是O(n)-比O(n log n)更快。 最初，软堆被用作构建最小生成树算法的快速算法的构建模块。 它们还用于新算法的线性时间选择，这是自著名的中位数算法以来第一个确定性算法能够在线性时间内运行。 在这两种情况下，软堆被用于“近似”地对输入元素排序，以让算法得到近似排序序列的粗略逼近，此时该算法会执行一些额外的逻辑来补偿缺乏完美性。 您几乎肯定永远不会在实践中看到软堆堆被使用，但如果您确实找到了一个需要使用它的情况，请留下评论让我知道！
总结一下:
- 毁坏优先级是在完全排序(准确但慢)和任意排序(不准确但非常快)之间做出权衡的一种方法。 参数ε决定破坏程度在谱上的位置。 - 破坏以改变软堆中现有元素的优先级为方式进行，特别是提高某些元素的优先级。 低度破坏对应近似排序的序列，而高度破坏对应于更任意的序列。 - 进行破坏的方法是与数据结构有关的，并且非常难理解。 最好将软堆看作在需要时执行破坏，但永远不会超过由选择ε所施加的限制的方式。 - 在理论环境中，当排序速度太慢，但近似正确排序序列足以满足实际需要时，破坏是有用的。 它在实践中不太可能有用。
希望这可以帮到您！
因为优先队列以优先级递增的顺序出队元素，所以它们可以用来对值序列进行排序 - 首先将每个元素插入到优先队列中，其优先级等于其在序列中的排名，然后从优先队列中将所有元素出队。这样就能以排序的方式取出元素。
然而，优先队列和排序之间的这种关联是有代价的。已知比较排序算法存在下限（没有比较排序算法的运行时间可以达到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的原始论文和后来基于二叉树进行的清理）使用称为拼车的技术对元素进行分组，并且所有元素共享一个公共优先级。由于每个组中所有元素的原始优先级被遗忘，并使用新的优先级，因此发生了破坏。元素分组的实际细节非常复杂，而且不值得深入研究，因此最好将其保留为“数据结构选择任意方式进行破坏，只要它不损坏超过您选择ε时指定的元素即可。”接下来，这有什么用处呢？ 实际上，几乎没有。 软堆heap几乎完全是理论性的。 之所以在理论上很好，是因为如果选择正确的ε，从软堆中进行n次插入和n次删除的运行时间可以是O(n)-比O(n log n)更快。 最初，软堆被用作构建最小生成树算法的快速算法的构建模块。 它们还用于新算法的线性时间选择，这是自著名的中位数算法以来第一个确定性算法能够在线性时间内运行。 在这两种情况下，软堆被用于“近似”地对输入元素排序，以让算法得到近似排序序列的粗略逼近，此时该算法会执行一些额外的逻辑来补偿缺乏完美性。 您几乎肯定永远不会在实践中看到软堆堆被使用，但如果您确实找到了一个需要使用它的情况，请留下评论让我知道！
总结一下:
- 毁坏优先级是在完全排序(准确但慢)和任意排序(不准确但非常快)之间做出权衡的一种方法。 参数ε决定破坏程度在谱上的位置。 - 破坏以改变软堆中现有元素的优先级为方式进行，特别是提高某些元素的优先级。 低度破坏对应近似排序的序列，而高度破坏对应于更任意的序列。 - 进行破坏的方法是与数据结构有关的，并且非常难理解。 最好将软堆看作在需要时执行破坏，但永远不会超过由选择ε所施加的限制的方式。 - 在理论环境中，当排序速度太慢，但近似正确排序序列足以满足实际需要时，破坏是有用的。 它在实践中不太可能有用。
希望这可以帮到您！
- templatetypedef
4
谢谢，这帮了我很多。如果我有更好的声誉，我会点赞你的回答。再次感谢。 - kalibra
@kalibra 很高兴能帮忙！我花了很多时间来研究软堆，想分享一下我所学到的。 :-) - templatetypedef
使用二叉树进行清理非常容易理解。我相信这个版本是由Kaplan和Zwick完成的。 - JonNRb
非常好的总结，我从这个回答中学到了我想知道的关于软堆的一切。谢谢！ - nimcap
2
答案在第二页：
“软堆可以随时增加某些键的值。这些键以及相应的项被称为损坏的。损坏完全由数据结构自行决定，用户无法控制。当然，findmin返回当前最小键，它可能损坏也可能不损坏。好处是速度：在堆更新期间，项以“拼车”的形式一起移动，以节省时间。 从信息论的角度来看，损坏是降低存储在数据结构中的数据熵的一种方式，从而促进其处理。熵定义为以2为底的对数，不同键分配的数量（即键分配的均匀分布的熵）。为了看到这个想法的合理性，将其推向极限，并观察如果通过将每个键提高到`的值来损坏每个键，则键集将具有零熵，我们可以轻松地在常数时间内执行所有操作。有趣的是，软堆表明，复杂度不需要降至零才能变为常数。”
这是一个自我毁灭的数据结构吗？
“软堆可以随时增加某些键的值。这些键以及相应的项被称为损坏的。损坏完全由数据结构自行决定，用户无法控制。当然，findmin返回当前最小键，它可能损坏也可能不损坏。好处是速度：在堆更新期间，项以“拼车”的形式一起移动，以节省时间。 从信息论的角度来看，损坏是降低存储在数据结构中的数据熵的一种方式，从而促进其处理。熵定义为以2为底的对数，不同键分配的数量（即键分配的均匀分布的熵）。为了看到这个想法的合理性，将其推向极限，并观察如果通过将每个键提高到`的值来损坏每个键，则键集将具有零熵，我们可以轻松地在常数时间内执行所有操作。有趣的是，软堆表明，复杂度不需要降至零才能变为常数。”
这是一个自我毁灭的数据结构吗？
- user133536
1
那么在任何操作中，一个键的值会以概率ε随机增加一定量，对吗？此外，这如何使操作更快？如果这对您来说很明显，我很抱歉，但我真的很困惑。 - kalibra
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接