ソートアルゴリズムの中でも、ヒープソートは最悪ケースでもO(n log n)を保証しながら、追加メモリをほとんど使わないという優れた特性を持つアルゴリズムです。
ヒープ木（ヒープ構造）という特殊なデータ構造を活用することで、効率的なソートを実現します。
本記事では、ヒープソートの時間計算量がO(n log n)になる理由を丁寧に解説するとともに、ヒープ木の仕組み・優先度付きキューとの関係・不安定ソートとしての特性についても詳しく説明します。
計算量の理論から実装の基礎まで、ぜひ最後まで読んでみてください。
ヒープソートの計算量はO(n log n)（結論）
それではまず、ヒープソートの計算量がO(n log n)になる理由について解説していきます。
ヒープソートは大きく「ヒープ構築フェーズ」と「ソートフェーズ」の2段階で構成されます。
ヒープ構築フェーズでは、n個の要素からヒープ木を作成します。
一見O(n log n)かかりそうに見えますが、実はO(n)で構築できることが証明されています。
ソートフェーズでは、ヒープの最大値（根）を取り出して末尾に移動し、残りのn-1個の要素で再度ヒープ性質を回復する操作（ヒープダウン）をn-1回繰り返します。
1回のヒープダウンにかかる時間はO(log n)であり、これをn-1回繰り返すため、ソートフェーズ全体はO(n log n)です。
ヒープソートの計算量は最良・平均・最悪のすべてでO(n log n)が保証されます。クイックソートのように特定の入力でO(n²)に悪化することがなく、空間計算量もO(1)（in-place）という非常にバランスの取れたアルゴリズムです。
空間計算量はO(1)です。
ヒープソートは元の配列をヒープとして使うため、追加の補助配列が不要です。
ヒープ構築がO(n)になる理由
ヒープ構築の計算量がO(n)になることは、直感に反して見えるため丁寧に説明します。
配列の後半（葉ノード）はヒープダウン不要で、前半の内部ノードのみヒープダウンが必要です。
木の高さをhとすると、高さkのノードは最大n/2^(k+1)個存在し、各ノードのヒープダウンコストはO(k)です。
合計コスト = Σ(k=0 to log n) n/2^(k+1) × k
= n × Σ(k=0 to ∞) k/2^(k+1)
= n × 1 = O(n)
（等比級数の公式を使って収束することが示せる）
この結果、ヒープ構築はO(n)であり、ヒープソート全体の支配的な項はO(n log n)のソートフェーズになります。
時間計算量の全体まとめ
| フェーズ | 処理内容 | 計算量 |
|---|---|---|
| ヒープ構築 | 配列をmax-heapに変換 | O(n) |
| ソートフェーズ | 最大値取り出し＋ヒープダウン × n-1回 | O(n log n) |
| 全体 | ヒープ構築 ＋ ソートフェーズ | O(n log n) |
最良・平均・最悪のすべてでO(n log n)が成立し、この点はマージソートと同様です。
不安定ソートであることの意味
ヒープソートは不安定ソートです。
ヒープの根から要素を取り出して末尾と交換する操作の過程で、等しい値を持つ要素の相対順序が変わる可能性があります。
安定性が求められるデータ処理（複合ソートなど）ではヒープソートは不向きであり、その場合はマージソートを選ぶとよいでしょう。
ヒープ木の仕組みとヒープ性質
続いては、ヒープソートの核心であるヒープ木の仕組みとヒープ性質について確認していきます。
ヒープ木を理解することで、なぜヒープソートがO(n log n)で動作するのかがより明確になります。
ヒープ木とは何か
ヒープ木は「完全二分木」であり、かつ「ヒープ性質」を満たすデータ構造です。
完全二分木とは、最下段以外のすべてのレベルが埋まっており、最下段は左から詰めて埋められている二分木です。
ヒープ性質には2種類あります。
max-heap（最大ヒープ）は親ノードの値が子ノードの値以上であるという性質で、根が最大値になります。
min-heap（最小ヒープ）は親ノードの値が子ノードの値以下であるという性質で、根が最小値になります。
ヒープソートでは通常max-heapを使います。
配列によるヒープの表現
ヒープ木は配列を使って効率的に表現できます。
インデックス0始まりの配列でi番目のノードに対して、左の子はインデックス2i+1、右の子は2i+2、親は(i-1)//2で表されます。
例：配列 [9, 5, 7, 3, 4, 6] のmax-heap表現
インデックス：0 1 2 3 4 5
値 ：9 5 7 3 4 6
根（最大値）：9（index 0）
9の左の子：5（index 1）、右の子：7（index 2）
5の左の子：3（index 3）、右の子：4（index 4）
7の左の子：6（index 5）
この配列表現によって、ポインタなしでツリー構造を表現できるため、空間効率が非常に高いです。
ヒープダウン（sift-down）操作
ヒープダウンは、あるノードのヒープ性質が崩れたとき（親が子より小さくなったとき）に、そのノードを正しい位置まで下に移動させる操作です。
最悪でもヒープの高さlog nだけ移動すれば済むため、1回のヒープダウンはO(log n)です。
これがヒープソートのソートフェーズでO(n log n)となる根拠です。
ヒープソートの実装と優先度付きキューとの関係
続いては、ヒープソートの具体的な実装と、優先度付きキューとの密接な関係について確認していきます。
Pythonでの実装例
def heapify(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):
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)
return arr
このコードはin-placeで動作し、空間計算量はO(1)（再帰スタックを除く）です。
優先度付きキューとヒープの関係
優先度付きキュー（Priority Queue）は「常に最大（または最小）の優先度を持つ要素を先に取り出せる」データ構造です。
ヒープはこの優先度付きキューの最も一般的な実装手段です。
| 操作 | 優先度付きキュー（ヒープ実装）の計算量 |
|---|---|
| 最大値の取得（peek） | O(1) |
| 最大値の取り出し（pop） | O(log n) |
| 要素の挿入（push） | O(log n) |
| ヒープ構築（heapify） | O(n) |
Pythonではheapqモジュールがmin-heapを標準提供しており、最小値の取得・取り出しがO(1)・O(log n)で行えます。
優先度付きキューはダイクストラ法・A*探索・タスクスケジューリングなど多くの重要アルゴリズムで使われます。
ヒープソートとPythonのheapqの関係
Pythonのheapqモジュールを使うとheap_sort的な処理を簡潔に書けます。
import heapq
def heap_sort_py(arr):
heapq.heapify(arr) # O(n)でmin-heap構築
return [heapq.heappop(arr) for _ in range(len(arr))] # O(n log n)
ただしこの実装は補助リストを生成するため空間計算量はO(n)になります。
in-placeのヒープソートが必要な場合は前述の実装を使うとよいでしょう。
ヒープソートの他のO(n log n)ソートとの比較と使い分け
続いては、ヒープソートをマージソート・クイックソートと比較しながら、使い分けの指針を確認していきます。
マージソートとの比較
マージソートとヒープソートはどちらもO(n log n)の時間計算量を持ちますが、特性が異なります。
| 比較項目 | ヒープソート | マージソート |
|---|---|---|
| 時間計算量（最悪） | O(n log n) | O(n log n) |
| 空間計算量 | O(1) | O(n) |
| 安定性 | 不安定 | 安定 |
| キャッシュ効率 | 低い | 中程度 |
| 外部ソート適性 | 低い | 高い |
メモリが非常に限られている環境ではヒープソートが有利で、安定性や外部ソートが必要な場面ではマージソートが適しています。
クイックソートとの比較
クイックソートは平均O(n log n)でキャッシュ効率が高く、実測では最も高速なソートの一つです。
しかし最悪O(n²)のリスクがあります。
ヒープソートは最悪でもO(n log n)を保証するため、最悪ケースのパフォーマンスが重要なセキュリティクリティカルなシステムや組み込み環境でヒープソートが選ばれることがあります。
introsortというアルゴリズムはクイックソートを基本としながら、再帰が深くなるとヒープソートに切り替える設計になっており、両者の利点を組み合わせています。
ヒープソートが最も適している場面
ヒープソートが最も力を発揮するのは以下のような場面です。
まず「メモリが極端に制限されている環境」です。
O(1)の補助空間しか使わないため、組み込みシステムやメモリ制約の厳しい環境に向いています。
次に「最悪ケースのO(n log n)を保証したい場面」です。
リアルタイムシステムやセキュリティ用途でパフォーマンスの予測可能性が重要な場面に適しています。
また「大量データの上位k件を取得したい場面」では、n個のデータからk個の最大値を取り出すのにO(n + k log n)という効率的な処理が可能です。
まとめ
ヒープソートの時間計算量はO(n log n)であり、最良・平均・最悪のすべてのケースでこの計算量が保証されます。
空間計算量はO(1)で、in-placeで動作する点が大きな強みです。
ヒープ木というデータ構造を活用し、ヒープ構築O(n)とソートフェーズO(n log n)の2段階で処理します。
不安定ソートであるため安定性が必要な場面には不向きですが、メモリ制約が厳しい環境や最悪ケースの保証が必要なシステムでは非常に有効です。
優先度付きキューとの密接な関係も理解することで、ヒープの応用範囲がさらに広がるでしょう。
