高效缓存的堆排序堆。

Question

3

我正在进行一个项目，想要使用堆排序来对数据进行排序，因为我的项目非常注重最坏情况。我知道快速排序在平均情况下更快，但由于其最坏情况为O(n^2)，我无法在项目中使用它。

我想知道是否有任何缓存高效的堆可以用于堆排序，并且空间复杂度更小？缓存效率对堆排序和快速排序的影响如何？它对堆排序的影响有多大？是很大的影响还是微不足道的？

- asd

我建议使用Introsort。它尝试使用快速排序，但如果递归深度过大，则会退回到堆排序。检查您的语言库的排序实现：它可能已经使用了混合算法，如Introsort或TimSort。 - Jim Mischel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

"Funnel堆是一种缓存无关的堆，是普通堆的替代品。我不知道它们能否帮助解决问题，因为我从未对它们进行基准测试。

4元堆是一种d元堆，它们并没有被调整到适应特定的缓存大小，但比2元(即二进制)堆要好一些，因为它们更浅。如果你继续增加d，这种效果就不会继续发挥作用了，4或8很棒，但对于更高的d，每层的开销超过了从较少层数中获得的节省，变得更加显著。

堆排序的空间复杂度实际上已经达到了最优，因为假设您使用标准技术在原地将输入堆化，然后将结果放在那里，复杂度已经是O(1)。

"

关于经典的堆排序和快速排序，这里有一个不同的看法和有趣的回答。简而言之，不要只是重复旧的“快速排序比堆排序好”的说法，情况更加复杂。请点击此处和此链接查看详细信息。