ヒープソート完全ガイド：原理・擬似コード・計算量（O(n log n)）と実践的最適化
エバープレイ編集部ヒープソートとは
ヒープソート（Heapsort）は、配列をソートするための比較ベースのソートアルゴリズムの一つで、主に「二分ヒープ（バイナリヒープ）」という完全二分木を配列で表現するデータ構造を利用します。代表的な特徴は最悪計算時間が O(n log n) で安定性がないこと、そしてインプレース（追加メモリが O(1)）で実装可能な点です。実務では最悪ケース時間が保証される点や、優先度キュー操作と密接に関係する点で重要視されます。
基本原理と用いるデータ構造（ヒープ）
ヒープは一般に「最大ヒープ（max-heap）」または「最小ヒープ（min-heap）」として扱います。最大ヒープでは親ノードのキーが常に子ノードのキー以上であり、配列の先頭（根）が最大値になります。配列による表現では、0-index の場合に i の子は 2*i+1, 2*i+2、親は floor((i-1)/2) で求められ、完全二分木の性質を活かしてメモリ効率よく扱えます。
アルゴリズムの流れ（ヒープソートの構成）
- 1. 配列をヒープ（通常は最大ヒープ）に構築する（heapify）。
- 2. ヒープの根（最大値）と配列末尾の要素を交換し、ヒープサイズを1減らす。
- 3. 根に移動した要素を下へ「sift-down（heapify-down）」して再度ヒープ条件を回復する。
- 4. ヒープサイズが1になるまで 2–3 を繰り返す。
この結果、配列は昇順に整列します（最大ヒープを使った場合）。最初のヒープ構築を下から行うことで O(n) 時間で構築でき、以降の n−1 回の取り出しでそれぞれ O(log n) の操作を行うため、全体で O(n log n) になります。
主要処理の擬似コード
function heapSort(A):
n = length(A)
buildMaxHeap(A, n)
for end = n - 1 down to 1:
swap(A[0], A[end])
siftDown(A, 0, end) // end はヒープの新しいサイズ（exclusive）
function buildMaxHeap(A, n):
// 最後の非葉ノードから根まで
for i = floor(n/2) - 1 down to 0:
siftDown(A, i, n)
function siftDown(A, i, n):
while true:
left = 2*i + 1
right = 2*i + 2
largest = i
if left < n and A[left] > A[largest]: largest = left
if right < n and A[right] > A[largest]: largest = right
if largest == i: break
swap(A[i], A[largest])
i = largest
計算量と空間計算量
- 時間計算量（ビッグオー）: 最悪・平均・最良ともに O(n log n)。ただしヒープ構築は Floyd の方法を使うと Θ(n) で行える。
- 空間計算量: インプレース実装なら追加メモリは O(1)。再帰を使わない実装が一般的。
- 安定性: 安定ではない（同一キーの相対順序を保たない）。
なぜヒープ構築は O(n) か（直感）
単純に各ノードに対して最大高さ分の下げ操作（sift-down）を行うと考えると、一見 O(n log n) に見えますが、完全二分木では葉に近いノードが多数を占め、それらは下げる高さが短いという性質があります。Floyd のアルゴリズムでは下位ノードから順に sift-down を行うため、全体の比較回数の総和が O(n) になることが解析で示されます（各レベルでのノード数と最大高さの和が定数倍の n に抑えられるため）。
実装上の注意点と最適化
- 配列のインデックス設計（0始まり／1始まり）に注意する。計算式が変わる。
- swap の回数を減らすために、sift-down 中は親位置を保持して最後に格納する「ホール法（コピー法）」が有効な場合がある。
- d-ary ヒープ（子を d 個持つ）にすれば木の高さを低くでき、メモリ参照（キャッシュ）局所性を改善できるが、一回の下げ操作での比較は増える。
- 分割統治系（クイックソート）と比べたときの実行速度は、平均ではクイックソートが速いことが多い。ヒープソートはデータ局所性が悪く、キャッシュミスや分岐予測の面で不利になりやすい。
ヒープソートの利点と欠点
- 利点:
- 最悪計算時間が O(n log n) で保証される。
- 追加メモリがほとんど不要（インプレース）。
- 優先度キュー（push/pop）の基盤となるのでトップ k 問題やオンラインの最大値取得に直接応用できる。
- 欠点:
- 安定でない。
- 実行速度は実際のデータや実装次第でクイックソートやマージソートより遅くなることが多い（特にキャッシュ効率が悪い）。
- 順序がほぼ整っている場合でも適応的に早くならない（平均・最良とも Θ(n log n)）。
実用的な位置付けと派生アルゴリズム
実運用のライブラリ実装では、C++ の std::sort がクイックソート（またはその改良）にヒープソートのフォールバックを組み合わせた「イントロソート（Introsort）」を使うことで、平均的な高速性と最悪時の保証を両立させています。Java のプリミティブ型ソートや Python の組み込みソートは別のアルゴリズム（dual-pivot quicksort や TimSort）を採用していますが、ヒープを使った操作（make_heap / push_heap / pop_heap）は標準ライブラリでサポートされています。
また、ヒープソートの改良版や近縁アルゴリズムとして、Dijkstra の smoothsort（既に整列に近い入力に対して O(n) に近い性能を出す）など適応的なソートも研究されていますが、実装の複雑さや定数因子の問題で一般的ライブラリにはあまり使われていません。
応用例
- 優先度キューを用いたイベントシミュレーションやダイクストラ法の実装（ただし実用では二分ヒープ以外にフィボナッチヒープや二項ヒープなども検討される）。
- 上位 k 件（Top-K）の抽出：全ソートよりもヒープを使った方法の方が効率的（例えばサイズ k のミニマムヒープを保持して走査する方法）。
- メモリ制約が厳しい環境でのソート（外部メモリを使う場合は別アルゴリズムが必要だが、内部メモリだけで済ませたい場合に有用）。
まとめ（どう使うべきか）
ヒープソートは「最悪ケース時間が保証されたインプレースソート」を求める場面で重要な選択肢です。日常的な高速ソート実装ではクイックソートや TimSort の方が速く、安定性を求めるならマージソートや TimSort を選びますが、最悪時間の上限や優先度キューの操作と組み合わせた利用など、設計上ヒープの性質を活かす場面は依然として多いです。
参考文献
- ヒープソート - 日本語 Wikipedia
- ヒープ (データ構造) - 日本語 Wikipedia
- Heapsort - Wikipedia (英語)
- Introsort - Wikipedia (英語)
- Smoothsort - Wikipedia (英語)
- Heap Sort — GeeksforGeeks (英語、実装と解析)
- std::make_heap / std::push_heap / std::pop_heap — cppreference (英語)
投稿者プロフィール
