Time and Space Complexity

時間計算量:

• 最良、平均、最悪の場合: O(n log n)
  • ヒープの構築は O(n) であり、n 回の抽出のそれぞれにおいて sift-down に O(log n) のコストがかかります。パフォーマンスを低下させるような最悪の入力ケースは存在しません。

空間計算量:

• O(1)
  • ヒープソートは元の配列内で要素を並べ替え、一定量の追加メモリのみを必要とします。

まとめ:

• ヒープソートは、保証された O(n log n) の実行時間と O(1) の追加空間を兼ね備えており、これはマージソートとクイックソートの両方が提供しているわけではない組み合わせです。
• 安定ではありません（同じ値の要素の相対的な順序が変わる可能性があります）。これが主なトレードオフです。