algorithm - ヒープ ツリー - ソートされたリストを出力する複雑さ

Question

番号のソートされていないリストがあり、それらからヒープ ツリーが構築されます。

既に構築されているヒープ ツリーからソートされた数値のリストを出力する時間の計算量はどれくらいですか?

(注: 現在の最小値/最大値を取得するためにノードをツリーから削除する必要はありません。ヒープ ツリーを走査し、並べ替えられた数値のリストを出力する効率的な方法を探します)

Answer 1

リストを最初にソートするのと同じ - O(nlogn)。これは、リストのヒープ化に O(n) 時間がかかり、並べ替えられたシーケンスを O(nlogn) よりも速くヒープから出力することは不可能であるためです。ヒープ化してから出力する)、これは間違っていることが証明されています。

Answer 2

これは、ヒーププロパティ（Cormen）を使用してソートされた順序でツリーを印刷するための重複した質問です。なぜそれがnlogn操作であり、ではないのかという元の質問で提供されたイラストがありlognます。