sorting - 堆排序：为什么不使用“软堆”来提高性能？

Question

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

谢谢！

Answer 1

软堆遭受“损坏”（阅读您链接到的页面），这使得它不能用作通用排序例程的组件。大多数时候你只会得到错误的答案。

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

斐波那契堆不会遭受“损坏”，但它有 O(log n) 删除时间。您可以将斐波那契堆用作通用排序例程的一部分，但排序的整体性能将是 O(n log n)。

Answer 2

跟进@Rob的观点：

基于比较的排序算法的效率存在理论上的限制，堆排序就是其中之一。 在平均情况下，没有任何基于比较的排序的运行时间比 Ω(n log n) 更好。由于堆排序是 Θ(n log n)，这意味着它是渐近最优的，并且不可能有 O(n) 平均时间变量（至少，不是基于比较的变量）。这个论点的证明来自信息论——如果不进行至少 Ω(n log n) 比较，就无法可靠地区分输入排列与任何其他输入排列。

软堆是通过从二项式堆开始并破坏部分键来发明的，这样从软堆中插入和出队 n 个元素不一定对它们进行排序。（关于软堆的原始论文在其摘要中提到，结构的独创性是人为地降低了存储值的“熵”以击败 Ω(n log n) 障碍）。这就是软堆可以支持 O(1) 时间操作的原因：与普通堆结构不同，它并不总是排序，因此不受上面给出的运行时障碍的约束。因此，n 个对象可以在 O(n) 时间内从软堆入队和出队这一事实立即表明您不能使用软堆来加速堆排序。

更一般地，没有办法使用任何基于比较的数据结构来构建排序算法，除非您在使用该数据结构时平均至少做了 Ω(n log n) 工作。例如，这个较早的问题解释了为什么您不能在 O(n) 时间内将二进制堆转换为 BST，因为这样做会让您在 O(n) 时间内纯粹使用比较进行排序（在 O(n) 中构建堆) 时间，然后在 O(n) 时间内转换为 BST，然后在 O(n) 时间内进行中序遍历以恢复已排序的序列）。

希望这可以帮助！