ヒープソートとは？
ヒープソート(Heap Sort)は、配列を最大ヒープ(max-heap)にしてから、最大値であるルートを末尾へ取り出す作業を繰り返す整列です。追加配列なしでその場整列しながら、入力に関係なく常にO(n log n)を保証します。
核心の一行: 「最大値を速く取り出して後ろから積む」。 ヒープは最大値をO(1)で確認しO(log n)で取り出せる構造なので、これをn回繰り返すと整列が完成します。
まず、ヒープ構造の復習
配列を完全二分木として見ます。インデックス i に対して
- •左の子 =
2i + 1、右の子 =2i + 2 - •親 =
(i - 1) / 2
最大ヒープは「すべての親が子以上」という規則を守る木なので、ルート(インデックス0)が常に全体の最大値です。
動作原理
ステップ1. ヒープ構築(build heap). 最後の親ノードからインデックス0まで逆向きに、各ノードにsift-down(heapify)を適用して配列全体を最大ヒープにします。これはO(n)です。
ステップ2. 最大値の取り出し. ルート(arr[0])とヒープの末尾要素を交換し、最大値を配列末尾の定位置へ送ります。
ステップ3. ヒープの復元. ヒープサイズを1減らし、ルートからsift-downを1回行って最大ヒープ性を復元します。
ステップ4. ヒープサイズが1になるまでステップ2〜3を繰り返します。後ろから大きな値が積まれ昇順になります。
AlgoNoteの可視化は「ヒープ構築」と「取り出し&復元」を別ステップで示すので流れが一目でわかります。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n log n) |
| 空間 | O(1) |
ヒープ構築はO(n)、その後のn回の取り出しが各O(log n)なので全体はO(n log n)です。マージソートのように常にO(n log n)を保証しつつ、追加配列なしでその場整列するため空間はO(1)です。
例で追ってみる
[3, 1, 4, 1, 5] を最大ヒープにするとルートに 5 が来ます。
- •
5と末尾を交換 → 末尾に5確定、復元 → ルート4 - •
4と末尾から2番目を交換 →...4 5、復元 → ルート3 - •繰り返すと
[1, 1, 3, 4, 5]完成
毎回「現在のヒープの最大値」が抜けて後ろから整列されます。
よくあるミス
- •sift-down/upの混同: 整列段階でルートを沈めるときはsift-downです。挿入(押し上げ)と混同しないように。
- •ヒープサイズの管理: 既に取り出した要素(整列済みの末尾)をヒープ範囲に再び含めると整列が壊れます。
- •子インデックスの式:
2i+1/2i+2の範囲チェックを忘れると配列外を参照します。
AlgoNoteで直接確認しましょう
配列が最大ヒープになり、ルートが末尾へ抜け、ヒープが再編成される過程をAlgoNoteでステップごとに確認できます。