ヒープソート：二分ヒープを使用したソート
ヒープソートが最大ヒープを使用して配列をO(n log n)時間でインプレースソートする方法を学びます。ヒープ構築フェーズ、抽出フェーズを理解し、クイックソートやマージソートと比較します。
Heap
詳細な説明
ヒープソートアルゴリズム
ヒープソートは二分ヒープを使用して配列をソートします。最悪ケースO(n log n)の時間計算量を持ち、O(1)の追加スペースでインプレースソートします。
アルゴリズムのステップ
- 入力配列から最大ヒープを構築 — O(n)
- 最大値を繰り返し抽出：ルート（最大値）と最後の未ソート要素を交換、ヒープサイズを1減らし、新しいルートをバブルダウンしてヒープ特性を回復。
他のソートとの比較
| アルゴリズム | 平均 | 最悪 | スペース | 安定 |
|---|---|---|---|---|
| ヒープソート | O(n log n) | O(n log n) | O(1) | いいえ |
| クイックソート | O(n log n) | O(n²) | O(log n) | いいえ |
| マージソート | O(n log n) | O(n log n) | O(n) | はい |
ヒープソートの利点：O(1)スペースで保証されたO(n log n)最悪ケース。 ヒープソートの欠点：クイックソートと比較してキャッシュパフォーマンスが悪い。
ヒープソートを使用すべき場合
- 最悪ケースO(n log n)が必要な場合（リアルタイムシステム）
- O(1)追加スペースが必要な場合
- 安定性が不要な場合
- フォールバックとして：多くの標準ライブラリソートはイントロソートを使用（再帰深度が深くなりすぎるとヒープソートにフォールバック）
ユースケース
ヒープソートは保証されたO(n log n)パフォーマンスが重要でメモリが限られたシステムで使用されます。Linuxカーネルは特定の内部操作にヒープソートを使用します。イントロソート（C++ std::sortやRustのsortで使用）はクイックソートの再帰深度がしきい値を超えるとヒープソートに切り替え、クイックソートの速度とヒープソートの最悪ケース保証を組み合わせます。