performance - ヒープソートを使用して、順序付けられていない数値のセットを線形時間でソートできますか?

Question

ねえみんな簡単な質問..

ご存知のように、順序付けされていない数値のセットから線形時間でヒープを構築できます。誰でも証明できますか？

前もって感謝します ！

Answer 1

いいえ。

線形 (O(n)) 時間でヒープ (おそらく完全なバイナリ ツリーとして実装) を構築できますが、ヒープの不変性を維持するために、ヒープからの各抽出には O(log(n)) の時間がかかります。したがって、バイナリ ヒープからの並べ替えられた配列のアセンブリには、すべての最適なバイナリ比較ベースの並べ替えアルゴリズムと同様に、合計で O(n log(n)) の時間がかかります。