ヒープソート (Heap Sort)

1. ヒープソートとは
2. ヒープとは
3. ヒープソートのアルゴリズム
4. ヒープソートの動作例
1. フェーズ1: ヒープの構築
2. フェーズ2: ソート
5. ヒープソートのシミュレーション
6. ヒープソートの特徴
1. 利点:
2. 欠点:
7. ヒープソートの応用
8. まとめ
9. その他のソート

1. ヒープソートとは

ヒープソートは、1964年にロバート・W・フロイドによって発明された効率的なソートアルゴリズムです。このアルゴリズムは、「ヒープ」というデータ構造を利用して配列をソートします。最悪、平均、最良のケースでも時間計算量が O(n log n) という特徴があり、安定したパフォーマンスを持っています。

2. ヒープとは

ヒープは完全二分木の一種で、以下の特性を持ちます。

完全二分木構造: すべてのレベルが完全に埋まっているか、最下層のみ左から右へ部分的に埋まっている二分木です。
ヒープ条件:
- 最大ヒープ: 各ノードの値がその子ノードの値以上
- 最小ヒープ: 各ノードの値がその子ノードの値以下

ヒープは配列で効率的に表現できるのが特徴です。配列内のインデックス i のノードに対して、

親ノードのインデックス: Math.floor((i - 1) / 2)
左の子ノードのインデックス: 2 * i + 1
右の子ノードのインデックス: 2 * i + 2

3. ヒープソートのアルゴリズム

ヒープソートは大きく分けて2つのフェーズから構成されています。

フェーズ1: ヒープの構築（Build Max Heap）

最初に、ランダムな配列を最大ヒープに変換します。

function buildMaxHeap(array) {
  const n = array.length;
  
  // 葉ノード以外の各ノードに対してmaxHeapify操作を行う
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(array, i, n);
  }
}

フェーズ2: 最大値の抽出と配置

構築したヒープから、根（最大値）を取り出して配列の末尾に配置し、ヒープのサイズを1つ減らして再構築します。これを繰り返すことで、配列は昇順にソートされます。

function heapSort(array) {
  // ヒープを構築
  buildMaxHeap(array);
  
  // ヒープから要素を1つずつ取り出して配置
  for (let i = array.length - 1; i > 0; i--) {
    // 根（最大値）を配列の末尾に移動
    [array[0], array[i]] = [array[i], array[0]];
    
    // ヒープを再構築
    maxHeapify(array, 0, i);
  }
}

maxHeapify 操作

最大ヒープの条件を維持するための核となる操作です。指定されたノードとその子ノードを比較し、必要に応じて値を交換します。

function maxHeapify(array, i, heapSize) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;
  
  // 左の子ノードと比較
  if (left < heapSize && array[left] > array[largest]) {
    largest = left;
  }
  
  // 右の子ノードと比較
  if (right < heapSize && array[right] > array[largest]) {
    largest = right;
  }
  
  // 最大値が現在のノードでない場合、交換して再帰的に処理
  if (largest !== i) {
    [array[i], array[largest]] = [array[largest], array[i]];
    maxHeapify(array, largest, heapSize);
  }
}

4. ヒープソートの動作例

配列 [4, 10, 3, 5, 1] をヒープソートで昇順にソートする過程を見てみましょう。

フェーズ1: ヒープの構築

初期配列: [4, 10, 3, 5, 1]
インデックス 1（値：10）から maxHeapify 開始:
- 10 は既に子ノード（5, 1）より大きいので変更なし
インデックス 0（値：4）から maxHeapify 開始:
- 4 < 10 なので交換: [10, 4, 3, 5, 1]

ヒープ構築完了: [10, 4, 3, 5, 1]（最大ヒープ）

フェーズ2: ソート

根（10）を末尾と交換: [1, 4, 3, 5, 10]
- ヒープサイズを4に減らし、maxHeapify: [5, 4, 3, 1] | 10
根（5）を末尾と交換: [1, 4, 3, 5] | 10 → [3, 4, 1] | 5, 10
- ヒープサイズを3に減らし、maxHeapify: [4, 3, 1] | 5, 10
根（4）を末尾と交換: [1, 3, 4] | 5, 10 → [3, 1] | 4, 5, 10
- ヒープサイズを2に減らし、maxHeapify: [3, 1] | 4, 5, 10
根（3）を末尾と交換: [1] | 3, 4, 5, 10 → [1, 3, 4, 5, 10]

最終的にソートされた配列: [1, 3, 4, 5, 10]

5. ヒープソートのシミュレーション

6. ヒープソートの特徴

利点:

時間計算量: 最悪、平均、最良のケースでも O(n log n)
空間計算量: O(1)（追加のメモリをほとんど使わない）
安定性: パフォーマンスが入力配列の状態に依存しない

欠点:

安定ソートではない: 同じ値の要素の相対的な順序が保持されない
キャッシュ効率: 要素間の移動が大きいため、キャッシュ効率が悪い場合がある
比較回数: クイックソートに比べて実際の比較回数が多い傾向

7. ヒープソートの応用

ヒープソートは、以下のような状況で特に有用です：

限られたメモリ環境: 追加のメモリをほとんど使わないため
最悪のケースの保証が必要な場合: 常に O(n log n) の時間計算量を保証
部分ソート: 最大/最小の k 個の要素だけを必要とする場合（k-選択問題）
優先度キュー: ヒープはデータ構造としても重要で、優先度キューの実装に使用される

8. まとめ

ヒープソートは、ヒープという特殊なデータ構造を利用した効率的なソートアルゴリズムです。二分ヒープの特性を活用することで、一貫したパフォーマンスを発揮し、追加のメモリもほとんど使わないという利点があります。アルゴリズムは比較的シンプルで、実装も容易なため、多くのシステムやライブラリで採用されています。

最悪のケースでも O(n log n) の時間計算量を保証する点は大きな強みですが、実際のパフォーマンスではクイックソートやマージソートに劣ることも多いため、具体的な用途や制約に合わせて適切なソートアルゴリズムを選択することが重要です。