algorithm - 堆树 - 输出排序列表的复杂性

Question

有一个未排序的数字列表，并从中构建了一个堆树。

从已经构建的堆树中输出排序的数字列表的时间复杂度是多少？

（注意：不需要从树中移除节点来获取当前的最小值/最大值，寻找一种有效的方法来遍历堆树并输出排序后的数字列表）

Answer 1

与最初对列表进行排序相同 - O(nlogn)。这是因为堆积列表需要 O(n) 时间，并且不可能比 O(nlogn) 更快地从堆中打印排序序列，因为这意味着可以比 O(nlogn) 更快地对任何序列进行排序（通过heapifying 然后输出），这被证明是错误的。

Answer 2

这是使用堆属性 (Cormen) 按排序顺序打印树的重复问题。原始问题中提供了一个说明，说明为什么它是一项nlogn操作而不是logn。