sorting - 堆排序:为什么不使用 "Soft Heap"来提高性能？

Question

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

谢谢!

Answer 1

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

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

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