performance - 我们可以使用 heapsort 在线性时间内对一组无序的数字进行排序吗？

Question

嘿伙计们快速提问..

正如我们所知，我们可以在线性时间内从一组无序的数字中构建一个堆。谁能证明如何？

提前致谢 ！

Answer 1

不。

虽然您可以在线性 (O(n)) 时间内构建一个堆（可能实现为完整的二叉树），但从堆中提取的每次都需要 O(log(n)) 时间以保持堆不变。因此，从二进制堆组装排序数组总共需要 O(n log(n)) 时间，就像所有基于最佳二进制比较的排序算法一样。