performance - 堆排序是否曾经在实践中使用过？

Question

在实践中，快速排序优于堆排序。Mergesort 是 3 个中唯一稳定的一个（在普通的实现中）。因此，根据手头的情况（在内存中就地或外部排序等）使用快速排序或合并排序

那么，是否存在确实使用堆数据结构进行排序的情况？无论我多么“谷歌”或尝试提出应用程序，几乎总是有人选择合并/快速排序而不是堆排序。我也从未遇到过在我的职业生涯中实际使用堆排序的情况。出于好奇，在实践中（如果有的话）堆排序实际上是一个好的用例吗？

Answer 1

我想到了一些好处（在我做更多研究后会修改这个列表：

• 几乎排序的集合受益于堆排序。
• 注重空间的环境通常更喜欢堆排序的 O(1) 空间复杂度。想想嵌入式系统。
• 巨大的数据集受益于O(nlog n)的保证运行时间，而不是快速排序可能更好的运行时间。想想医疗、空间、生命支持等。