ヒープ — 優先順位キューの原理
このトピックを修了すると
ヒープの構造と動作原理を説明でき、Pythonのheapqを使って優先順位キューを実装し、「最も小さい（または大きい）値を素早く取り出す」問題を解決できるようになります。
問題 — 「最も緊急なもの」を素早く取り出す
病院の救急外来を考えてみましょう。患者が到着した順番（キュー）ではなく、症状の深刻度に応じて治療の順番が変わります。このような「優先順位が付けられたキュー」をどのように実装すればよいでしょうか？
- ソートされたリスト：挿入するたびにソート → O(n)
- ソートされていないリスト：最小値を検索する際に全件検索 → O(n)
ヒープは、挿入と最小値の抽出を**O(log n)**で行います。
ヒープの規則
最小ヒープ(Min Heap)の規則は単純です。
親は常に子よりも小さいか等しい
1 ← 最小値は常にルート
/ \
3 5
/ \ / \
7 4 8 6ルートには常に最も小さい値があるので、最小値をO(1)で確認できます。
BSTとの違い：BSTは「左 < 親 < 右」ですが、ヒープは「親 < 子」を守るだけです。兄弟間の順序は関係ありません。
配列で表現する
ヒープは木構造ですが、実際には配列で保存します。
インデックス: [0, 1, 2, 3, 4, 5, 6]
値: [1, 3, 5, 7, 4, 8, 6]親インデックス i に対して：
左の子 = 2*i + 1
右の子 = 2*i + 2
親 = (i - 1) // 2インデックス0の子：1, 2 / インデックス1の子：3, 4 / インデックス2の子：5, 6。ポインタなしでインデックス計算のみで親-子の関係を把握できます。
挿入と削除の原理
挿入 (heappush)：配列の末尾に追加し、親と比較しながら上に移動します（sift up）。
初期： [1, 3, 5, 7, 4, 8, 6]
2 を挿入：[1, 3, 5, 7, 4, 8, 6, 2]
↑ インデックス7の親(3) = インデックス3(値 7)
2 < 7 → 交換：[1, 3, 5, 2, 4, 8, 6, 7]
↑ インデックス3の親 = インデックス1(値 3)
2 < 3 → 交換：[1, 2, 5, 3, 4, 8, 6, 7]
↑ インデックス1の親 = インデックス0(値 1)
2 > 1 → 停止削除 (heappop)：ルートを削除し、最後の要素をルートに置き、子と比較しながら下に移動します（sift down）。これらの2つの操作は、木の高さの分だけ移動するため、O(log n)です。
Python heapq
Pythonはheapqモジュールで最小ヒープを提供します。
import heapq
# 空のリストをヒープとして使用heap = []
# 挿入 — O(log n)heapq.heappush(heap, 5)heapq.heappush(heap, 3)heapq.heappush(heap, 7)heapq.heappush(heap, 1)
print(heap) # [1, 3, 7, 5] — 内部の順序はヒープの規則に従うprint(heap[0]) # 1 — 最小値は常にインデックス 0
# 最小値の抽出 — O(log n)smallest = heapq.heappop(heap)print(smallest) # 1print(heap) # [3, 5, 7]heappushとheappopを覚えておけばOKです。
既存のリストをヒープに変換する
data = [9, 1, 4, 7, 2, 8, 3]heapq.heapify(data) # O(n) — ソート(O(n log n))よりも高速print(data) # [1, 2, 3, 7, 9, 8, 4]heapifyはリストをその場でヒープに変換します。
優先順位キューの実装
import heapq
class PriorityQueue: def __init__(self): self.heap = [] def push(self, priority, item): heapq.heappush(self.heap, (priority, item)) def pop(self): return heapq.heappop(self.heap)[1] def is_empty(self): return len(self.heap) == 0
# 救急外来の例er = PriorityQueue()er.push(3, "風邪の患者")er.push(1, "心停止の患者") # 優先順位1が最も緊急er.push(2, "骨折の患者")
print(er.pop()) # "心停止の患者"print(er.pop()) # "骨折の患者"print(er.pop()) # "風邪の患者"タプルの最初の要素が比較基準になります。数値が小さいほど優先順位が高くなります。
最大ヒープが必要な場合
Pythonのheapqは最小ヒープのみを提供します。最大ヒープが必要な場合は、値を負の数にして入れます。
# 最大ヒープの効果max_heap = []for val in [3, 1, 5, 2, 4]: heapq.heappush(max_heap, -val)
print(-heapq.heappop(max_heap)) # 5 (最も大きい値)print(-heapq.heappop(max_heap)) # 4便利な関数
data = [7, 3, 9, 1, 5, 8, 2]
# 最小の3つprint(heapq.nsmallest(3, data)) # [1, 2, 3]
# 最大の3つprint(heapq.nlargest(3, data)) # [9, 8, 7]
# ソートされた複数のリストを1つに結合a = [1, 4, 7]b = [2, 5, 8]c = [3, 6, 9]print(list(heapq.merge(a, b, c))) # [1, 2, 3, 4, 5, 6, 7, 8, 9]時間計算量のまとめ
| 演算 | 時間計算量 |
|---|---|
| 挿入 (heappush) | O(log n) |
| 最小値の抽出 (heappop) | O(log n) |
| 最小値の確認 (heap[0]) | O(1) |
| ヒープの構築 (heapify) | O(n) |
| 目的 | データ構造 |
|---|---|
| 正確なキーで検索 | ハッシュテーブル |
| ソートされた順序を維持 | BST |
| 最小値/最大値のみを素早く | ヒープ |
ヒープソート
ヒープを使ってソートできます。
def heap_sort(arr): heapq.heapify(arr) # O(n) return [heapq.heappop(arr) for _ in range(len(arr))]
data = [7, 3, 9, 1, 5]print(heap_sort(data)) # [1, 3, 5, 7, 9]時間計算量はO(n log n)で、クイックソート、マージソートと同等です。実際にはPythonのsorted()（Timsort）の方が高速ですが、概念的にヒープソートの原理を理解することが重要です。
実践 — Top K 問題
「100万件のデータから最も大きい10件」を求める問題。
import heapq
data = [random.randint(0, 1_000_000) for _ in range(1_000_000)]
# ❌ 全体をソート — O(n log n)top10_sort = sorted(data, reverse=True)[:10]
# ✅ ヒープを使用 — O(n log k)top10_heap = heapq.nlargest(10, data)全体をソートするとO(n log n)ですが、ヒープはサイズkだけを維持するため、O(n log k)です。kがnよりもはるかに小さい場合に大きな違いがあります。
# 自分で実装すると原理がわかりますmin_heap = []for val in data: if len(min_heap) < 10: heapq.heappush(min_heap, val) elif val > min_heap[0]: heapq.heapreplace(min_heap, val)
top10 = sorted(min_heap, reverse=True)サイズ10の最小ヒープを維持します。新しい値がヒープの最小値よりも大きい場合は、置き換えます。最後に残った10個が全体で最も大きい10個です。
実践 — ダイクストラ法
最短経路アルゴリズムであるダイクストラ法もヒープを使用します。
def dijkstra(graph, start): dist = {node: float('inf') for node in graph} dist[start] = 0 heap = [(0, start)] while heap: cost, node = heapq.heappop(heap) if cost > dist[node]: continue for neighbor, weight in graph[node]: new_cost = cost + weight if new_cost < dist[neighbor]: dist[neighbor] = new_cost heapq.heappush(heap, (new_cost, neighbor)) return dist「まだ訪問していないノードの中で最も近いものを」毎回取り出す必要があるため、ヒープがないとO(V²)になり、ヒープを使うとO((V+E) log V)で動作します。
ヒープは、「全体をソートする必要はなく、最も重要なものを1つだけ素早く取り出せばよい」という状況に最適です。