xuh*_*dev 7 sorting heap heapsort data-structures soft-heap
在Soft Heap维基百科页面中,似乎min提取只需要持续时间,因此使用软堆来执行heapsort应该导致摊销的O(n).即使常数很大,对于非常大的n,这个算法应该非常有用.但我从未听过有人提到这一点.是否有人不使用此功能？
谢谢!
Soft Heap遭受"腐败"(阅读您链接的页面),这使其不适用于通用排序例程的组件.你大部分时间都会得到错误的答案.
如果你有一些需要排序但可以处理"损坏"结果的应用程序,你将从软件堆中获得作为实现的一部分,那么这将为你提供潜在的加速.
Fibonacci Heap不会遭受"损坏",但它有一个O(log n)删除时间.您可以将Fibonacci Heap用作通用排序例程的一部分,但排序的整体性能将为O(n log n).