堆排序:为什么不使用“软堆”来提高性能呢？

Question

从Soft Heap维基百科的页面上看，最小值提取似乎只需要恒定的时间，因此使用软堆执行堆排序应该会产生一个摊销的O(n)。即使常数很大，对于非常大的n，这个算法也应该是非常有用的。但我从来没听人提到过这个。人们不使用它有什么原因吗？

谢谢!

Answer 1

软堆存在“损坏”问题(请阅读您链接的页面)，这使得它不适用于作为通用排序例程的组件。大多数情况下，你只会得到错误的答案。

如果您有一些需要排序的应用程序，但可以处理作为实现一部分的软堆的“损坏”结果，那么这将为您提供潜在的加速。

Fibonacci堆没有“损坏”，但是它的删除时间是O(log )。您可以将Fibonacci Heap用作通用排序例程的一部分，但排序的总体性能将为O(n log n)。

Answer 2

要跟进@Rob的观点：

基于比较的排序算法的效率在理论上是有限制的，堆排序算法就是其中之一。No comparison-based sort can do have runtime better than Ω(n log n) in the average case。由于堆排序是Θ( not )，这意味着它是渐近最优的，并且不可能存在O(n)平均时间变量(至少不是基于比较的变量)。这个论点的证据来自信息论-如果不进行至少Ω( no )比较，就没有办法可靠地将输入排列与任何其他输入排列区分开来。

软堆是通过从二项式堆开始并破坏一些键的片段来发明的，使得从软堆中插入和出列n个元素不一定对它们进行排序。(The original paper on soft heaps在其摘要中提到，该结构的巧妙之处在于人为地降低了存储值的“熵”，以突破Ω( n )障碍)。这就是为什么软堆可以支持O(1)-time操作的原因:与普通的堆结构不同，它并不总是排序，因此不受上面给出的运行时障碍的约束。因此，n个对象可以在O(n)时间内从软堆入队和出队这一事实表明，您不能使用软堆来加速堆排序。

更广泛地说，没有办法使用任何基于比较的数据结构来构建排序算法，除非您在使用该数据结构时平均至少做了Ω( no )工作。例如，this earlier question解释了为什么不能在O(n)时间内将二进制堆转换为BST，因为这样做可以让您完全使用比较来在O(n)时间内进行排序(在O(n)时间内构建堆，然后在O(n)时间内转换为BST，然后在O(n)时间内进行顺序遍历以恢复排序后的序列)。

希望这能有所帮助！