ヒープソートの仕組みを徹底解説！アニメーションで学ぶ「砂山(heap)」ソート【ソートアルゴリズム入門】#11

マージソート、クイックソートに続く「第3の \(O[N \log N]\) ソート」

こんにちは！これまで、 \(O[n^2]\) の壁を超える高速なソートアルゴリズムとして、「分割統治法」に基づくマージソートとクイックソートを紹介してきました。

どちらも \(O[n \log n]\) という優れた計算量を持ちますが、

マージソートは、ソート済みリストを保持するための余分なメモリ領域が必要でした。
クイックソートは、ピボットの選び方次第で最悪 \(O[n^2]\) になる可能性を秘めていました。

今回紹介する「ヒープソート（Heap Sort）」は、これらとは全く異なるアプローチで \(O[n \log n]\) を達成するアルゴリズムです。

11 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...

ヒープソートの実行例アニメーション

ヒープソートは、「ヒープ（Heap）」と呼ばれる特殊なデータ構造を利用することで、余分なメモリ領域をほとんど使わずに（インプレース）、かつ最悪の場合でも \(O(N \log N)\) の計算量を維持できる、非常に優れたソートアルゴリズムです。

この記事では、ヒープソートの心臓部である「ヒープ」とは何か、そしてそれがどのようにソートに応用されるのかを図解していきます。

ヒープソート（Heap Sort）とは？

ヒープソートは、その名の通り「ヒープ (Heap)」というデータ構造を使ってソートを行うアルゴリズムです。

ヒープとは？

ヒープとは、「親ノードは、必ず子ノードより大きい（または小さい）」というルールを満たした木構造（ツリー）の一種です。（※ソートで使うのは通常「二分木」です）

最大ヒープ (Max Heap): 親が常に子より大きい。（例：根元（Root）が最大値）

最小ヒープ (Min Heap): 親が常に子より小さい。（例：根元が最小値）

昇順（小さい順）にソートしたい場合、最大ヒープを使います。「一番大きいもの」を常に見つけられるようにするためです。前回の記事でヒープについて紹介しています。

ヒープソート前座　ヒープとは？【ソートアルゴリズム入門】#10

ヒープとは？ヒープである条件について紹介。ヒープがわかればヒープシートがわかる。

ヒープソートは、大きく分けて以下の2つのフェーズで動作します。

フェーズ1: ヒープ構築 (Heapify)
- まず、ソートしたいバラバラの配列全体を、無理やり「最大ヒープ」のルールに従うように並び替えます。（配列を木構造とみなして操作します）
- この操作により、配列の先頭（ヒープの根元）が、データ全体の最大値になります。
フェーズ2: ソート（最大値の取り出しと再構築）
- (a) ヒープの根元（最大値）と、ヒープの末尾の要素を交換します。
- (b) これにより、配列の一番後ろに最大値が「確定」します。
- (c) 確定した要素（末尾）をヒープから除外し、ヒープのサイズを1つ減らします。
- (d) 根元に来た要素（元々末尾にあったもの）のせいでヒープのルールが崩れるので、ヒープを再構築して、再び根元に（残りの要素の）最大値が来るようにします。
- (e) (a)〜(d)を、ヒープの要素がなくなるまで繰り返します。

配列の後ろから順番に「最大値」「2番目に大きい値」「3番目に大きい値」…と確定していくイメージです。

ヒープソートで配列を並び替えたら？

では、実際のデータ [ 3, 5, 8, 1, 6, 2 ] を例に、ステップを見ていきましょう。

フェーズ1: 最大ヒープの構築 (Build Max Heap)

まず、この配列を「最大ヒープ」にします。

配列 [ 3, 5, 8, 1, 6, 2 ] は、以下のような木構造とみなすことができます。

（配列の i 番目の親は (i-1)/2、子は 2i+1 と 2i+2 で計算できます）

この木を、「最後の親（8）」から順番に「親 > 子」のルールを満たすように調整（ヒープ化）していきます。

ヒープ化が完了すると、配列は例えば [ 8, 6, 5, 1, 3, 2 ] のようになり、木構造は以下のようになります。

根元（8）が最大値になっていることに注目してください。

フェーズ2: ソート（最大値の取り出しと再構築）

ここからソート本番です。

1回目

根元（最大値 8）と、ヒープの末尾 2 を交換します。
- 配列: [ 2, 6, 5, 1, 3, 8 ]
8 がソート完了（確定）します。ヒープの範囲は [ 2, 6, 5, 1, 3 ] になります。
根元に来た 2 がルール違反なので、ヒープを再構築（Sift Down）します。
- 2 が下に沈んでいき、残りの最大値 6 が根元に上がってきます。
- ヒープ部分の配列: [ 6, 3, 5, 1, 2 ]

2回目

根元（最大値 6）と、ヒープの末尾 2 を交換します。
- 配列: [ 2, 3, 5, 1, 6, 8 ]
6 がソート完了（確定）します。ヒープの範囲は [ 2, 3, 5, 1 ] になります。
根元に来た 2 でヒープが崩れるので、再構築します。
- 5 が根元に上がってきます。
- ヒープ部分の配列: [ 5, 3, 2, 1 ]

3回目

根元（最大値 5）と、ヒープの末尾 1 を交換します。
- 配列: [ 1, 3, 2, 5, 6, 8 ]
5 がソート完了（確定）します。ヒープの範囲は [ 1, 3, 2 ] になります。
ヒープを再構築します。
- 3 が根元に上がってきます。
- ヒープ部分の配列: [ 3, 1, 2 ]

…これを繰り返すと、配列の後ろから [ ..., 1, 2, 3, 5, 6, 8 ] とソートが完了していきます。

ヒープソートの動きを見てみよう！

ヒープソートで並び替えを試せます。ヒープ配列は配列の中身、ツリー構造は今のヒープ配列を表しています。

「ランダム再配置」を押して、まずは配列全体が「最大ヒープ」に組み替えられる様子と、その後に根元（最大値）が次々と配列の末尾に送られていく様子を観察してみてください。

フェーズ: 待機中

配列: [ ]

リセットボタンを押してください

▼ ソート済み配列 (出力用)

「ランダム再配置」を押して開始してください。

ヒープソートの疑似コード (ソートの手順)

ヒープソートは、配列をヒープ化する関数（heapifyDown）が中心となります。

// L: ソートしたいリスト
algorithm HeapSort(L) is
  n ← length of L
  
  // (フェーズ1) 配列全体を最大ヒープにする (Build Max Heap)
  // (n/2 - 1) は「最後の親ノード」のインデックス
  for i from (n / 2 - 1) down to 0 do
    heapifyDown(L, n, i) // i を根とする部分木をヒープ化
  end
  
  // (フェーズ2) ソート
  // (n-1) から 1 まで (0は自動的にソートされる)
  for i from (n - 1) down to 1 do
    
    // (a) 根元(最大値) L[0] と、ヒープの末尾 L[i] を交換
    swap(L[0], L[i])
    
    // (d) ヒープのサイズを i に減らし、根元(0)から再構築
    heapifyDown(L, i, 0)
  end
  
  return L
end


// L: リスト, n: ヒープのサイズ, i: ヒープ化する部分木の根
algorithm heapifyDown(L, n, i) is
  
  largest ← i       // 親
  left ← 2*i + 1  // 左の子
  right ← 2*i + 2 // 右の子
  
  // (1) 左の子がヒープの範囲内(n)かつ、親より大きいか
  if left < n and L[left] > L[largest] then
    largest ← left
  end
  
  // (2) 右の子がヒープの範囲内(n)かつ、(現時点での)最大値より大きいか
  if right < n and L[right] > L[largest] then
    largest ← right
  end
  
  // (3) 最大値が親(i)でなかった場合 (つまり子が親より大きかった)
  if largest != i then
    swap(L[i], L[largest]) // 親と最大の子を交換
    
    // 交換した先（largest）で、さらにヒープ化を再帰的に行う
    heapifyDown(L, n, largest)
  end
end