この記事では、ソートアルゴリズムの一つであるヒープソートについて解説します。ヒープソートは、大量のデータを効率よく並べ替えることができるアルゴリズムです。この記事を読むことで、ヒープソートの基本的な仕組み、ヒープソートの具体的な手順、Pythonでのヒープソートの実装方法を理解することができる様になります。
ヒープソートとは
ヒープソートは、ヒープと呼ばれる特殊なデータ構造（完全二分木）を利用したソートアルゴリズムです。
完全二分木とは、木構造の一種で、以下の特徴を持ちます。
- すべての葉が同じ深さにあるか、一つ違いの深さにある
- 最後のレベル（一番下の段）を除いて、すべてのノードに子がいる（隙間なくノードが詰まっている）
ヒープは、完全二分木の中でも、以下の条件を満たすものです。（最大ヒープの場合）
- 親ノードの値は、常に子ノードの値以上である
このヒープの性質により、最大値（または最小値）を効率的に見つけ出すことができます。
ヒープソートの手順
ヒープソートは、以下の2つのステップでソートを行います。
- 与えられたデータをヒープ構造に変換する（ヒープ化）
- ヒープから最大値（または最小値）を取り出し、残りのデータを再度ヒープ化する。この操作を繰り返すことで、ソート済みの配列を得る。
ヒープソートは、最悪の場合でも計算量が O(n log n) となることが保証されている効率的なアルゴリズムです。
ヒープソートの仕組み
ここでは、配列 [12, 11, 13, 5, 6, 7] を例に、ヒープソートの手順を具体的に見ていきます。今回は最大ヒープを使います。
1. ヒープ化
まず、与えられた配列を最大ヒープに変換します。
- 初期状態:
12
/ \
11 13
/ \ /
5 6 7
インデックス2 (
13): 子を持たないので変更なし。インデックス1 (
11):11とその子5,6を比較。11が最大なので変更なし。インデックス0 (
12):12とその子11,13を比較。13が最大なので13と12を交換。
13
/ \
11 12
/ \ /
5 6 7
交換後の12の子7と比較し、12の方が大きいのでOK
これで、配列が最大ヒープの条件を満たすようになりました。木のルート（配列の先頭）が最大値になっています。
2. ソート
ヒープ化されたデータから、最大値を取り出して配列の末尾に移動させ、残りの部分を再度ヒープ化する、という操作を繰り返します。
- ステップ1: 最大値
13を末尾の7と交換。13はソート済みとする。
7
/ \
11 12
/ \ /
5 6
-ステップ２:
13を除いた部分[7, 11, 12, 5, 6]を再度ヒープ化。12と7を交換。
12
/ \
11 7
/ \
5 6
- ステップ3: 最大値
12を末尾の6と交換。12はソート済みとする。
6
/ \
11 7
/
5
-ステップ４:
12を除いた部分[6, 11, 7, 5]を再度ヒープ化。11と6を交換
11
/ \
6 7
/
5
- ステップ5: 最大値
11を末尾の5と交換。11はソート済みとする。
5
/ \
6 7
-ステップ６:
11を除いた部分[5, 6, 7]を再度ヒープ化。7と5を交換。
7
/ \
6 5
- ステップ7: 最大値
7を末尾の6と交換。7はソート済みとする。
6
/
5
-ステップ８:
7を除いた部分[6, 5]を再度ヒープ化。6と5を交換。
6 / 5
- ステップ9: 最大値
6を末尾の5と交換。6,5はソート済みとする。
5
最終的にソートされた配列: [5, 6, 7, 11, 12, 13]
このようにヒープソートを用いて、ソートを行うことができました。
Pythonでの実装例
def heapify(arr, n, i): """ 配列arrのi番目の要素をルートとする部分木を最大ヒープ化する Args: arr: ヒープ化する配列 n: 配列の要素数（ヒープ化する範囲） i: ルートとする要素のインデックス """ largest = i # 親ノード left = 2 * i + 1 # 左の子ノードのインデックス right = 2 * i + 2 # 右の子ノードのインデックス # 左の子が存在し、親ノードより大きい場合 if left < n and arr[left] > arr[largest]: largest = left # 右の子が存在し、親ノード（または左の子）より大きい場合 if right < n and arr[right] > arr[largest]: largest = right # 親ノードと最大の子ノードを交換（必要であれば） if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # 交換した子ノードをルートとして、再帰的にヒープ化 heapify(arr, n, largest) def heap_sort(arr): """ ヒープソートを実行する Args: arr: ソートする配列 """ n = len(arr) # 配列全体を最大ヒープ化 # 後ろから順に、各要素をルートとする部分木をヒープ化していく for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # ヒープから最大値を取り出し、配列の末尾に移動させる操作を繰り返す for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # 最大値（ルート）を末尾と交換 heapify(arr, i, 0) # 残りの部分を再度ヒープ化 # 使用例 arr = [12, 11, 13, 5, 6, 7] heap_sort(arr) print("ソート結果:", arr) # 出力: ソート結果: [5, 6, 7, 11, 12, 13]
このコードでは、heapify 関数で配列をヒープに変換し、heap_sort 関数で、ヒープから最大値を取り出しては末尾に移動するという操作を繰り返し行い配列全体をソートしています。このコードで肝となる処理は下記の2つです。
heapify(arr, n, i)配列arrの中で、インデックスiにある要素を親とする部分木が最大ヒープになるように操作します。nはヒープに含める要素の数です。 親と左右の子のインデックスを計算し、もし子が親よりも大きければ、それらの要素を交換します。交換が行われた場合は、交換された子の位置で再帰的にheapifyを呼び出し、ヒープの条件が満たされるまで続けます。heap_sort(arr)与えられた配列arrに対してヒープソートを適用します。 最初に、配列全体をヒープ構造にします。配列の後半部分から始めて、各要素に対してheapifyを適用し、配列をヒープに変換します。 ヒープが完成したら、最大要素（配列の最初の要素）を配列の最後に移動させ、ヒープサイズを1つ減らして再度heapifyを呼び出す、という処理を繰り返します。 これにより配列が小さい順に並び替えられます。
まとめ
ヒープソートは、データ構造「ヒープ」の特性を活かした効率的なソートアルゴリズムです。大量のデータを扱う場面で特に有用です。Pythonを使えば、比較的簡単にヒープソートを実装することができます。最後にPythonやITの基礎の学習に利用できるUdemy
のサイトを紹介します。ぜひ活用ください。
[PR]
