ヒープと優先度付きキュー入門 - O(log n)で最小・最大を取り出すデータ構造
日本語でヒープを丁寧に学べる良書。
競技プログラミングの定番。ヒープ実装が充実。
ヒープの理論を厳密に扱う網羅的教科書。
当サイトは Amazon.co.jp を宣伝しリンクすることで紹介料を得る手段を提供する、Amazonアソシエイト・プログラムの参加者です。価格・在庫はリンク先の最新情報をご確認ください。
ToDoリストの中から「いちばん急ぎの1件」だけをすばやく取り出したい——そんな場面はプログラミングのあちこちに現れます。毎回リスト全体を見渡して最小（または最大）を探すと O(n) かかりますが、優先度付きキューと、その代表的な実装である二分ヒープを使えば、取り出しも追加も O(log n) で済みます。この記事では、優先度付きキューという抽象データ型と二分ヒープの仕組みを、配列表現・sift-up / sift-down・計算量まで、Pythonの動くコードで順に整理します。最短経路を求めるグラフ探索アルゴリズム入門や、並べ替えのソートアルゴリズム入門と同じアルゴリズム入門シリーズの1本です。
優先度付きキューとは — 「次に処理すべき1件」を効率よく取り出す
優先度付きキュー（priority queue）は、具体的なデータの並べ方ではなく「どんな操作ができるか」を定めた抽象データ型（ADT）です。主な操作は次の通りです。
- insert / push: 要素を優先度つきで追加する
- extract-min / pop（または extract-max）: 優先度が最小（または最大）の要素を取り出して削除する
- peek / find-min / top: 取り出さずに先頭の要素だけを見る
- decrease-key（任意）: すでに入っている要素の優先度を下げる
ここで大事なのは、優先度付きキューは「操作の約束事」であって、内部の実装は自由だという点です。ソート済み配列でも、二項ヒープでも、平衡二分探索木でも実現できます。その中で二分ヒープが最もよく使われる実装というだけで、「優先度付きキュー＝二分ヒープ」ではありません。この区別を押さえておくと、言語ごとのライブラリの違いも整理して理解できます。
二分ヒープの仕組み — 完全二分木を配列で表す
二分ヒープ（binary heap）は、次の2つの性質を満たす木です。
- 完全二分木（complete binary tree）: 最下段を除くすべての段が埋まっていて、最下段は左詰めになっている
- ヒープ条件: min-heap では「親は子以下」で根が最小、max-heap では「親は子以上」で根が最大
注意したいのは、ヒープが定めるのは親子の大小関係だけ、という点です。兄弟どうしの大小は規定されない半順序なので、ヒープはソート済みではありません。「根が最小（または最大）であること」だけが保証されます。
完全二分木は隙間なく詰まっているため、ポインタを持つノードを作らなくてもただの配列で表せます。0-indexed（配列の添字が0から）なら、インデックス i のノードに対して次のように親子をたどれます。
- 親:
(i-1)//2 - 左の子:
2*i+1 - 右の子:
2*i+2 - 根: index 0
教科書（CLRS）でよく使われる1-indexed版なら、親が i//2、左の子が 2*i、右の子が 2*i+1、根が index 1 になります。どちらも掛け算・割り算だけで親子を行き来できるのがヒープの気持ちよさです。
push と pop — sift-up / sift-down（Pythonで自作）
ヒープの追加・取り出しは、2つの「玉突き」操作でできています。
- sift-up（up-heap / bubble-up）: push で使います。まず末尾に要素を足し、親と比べてヒープ条件を破っていれば交換して上へ運びます。木の高さのぶんだけ動くので
O(log n)です - sift-down（down-heap / bubble-down）: pop で使います。根を取り出したあと末尾の要素を根に置き、min-heapなら小さい方の子と比べて条件を破っていれば交換して下へ運びます。こちらも
O(log n)です
仕組みを体に入れるため、配列ベースのmin-heapを自作してみます。
class MinHeap:
def __init__(self):
self.data = [] # 0-indexed の配列で完全二分木を表す
def peek(self):
return self.data[0] # 根が最小、O(1)
def push(self, x):
self.data.append(x) # まず末尾に追加
self._sift_up(len(self.data) - 1) # 親と比べて上へ、O(log n)
def pop(self):
last = self.data.pop() # 末尾を取り出す
if not self.data:
return last # 要素が1つだけならそれが最小
root = self.data[0]
self.data[0] = last # 末尾を根へ移し
self._sift_down(0) # 子と比べて下へ、O(log n)
return root
def _sift_up(self, i):
while i > 0:
parent = (i - 1) // 2 # 親のインデックス
if self.data[i] < self.data[parent]:
self.data[i], self.data[parent] = self.data[parent], self.data[i]
i = parent
else:
break
def _sift_down(self, i):
n = len(self.data)
while True:
left, right = 2 * i + 1, 2 * i + 2 # 左の子・右の子
smallest = i
if left < n and self.data[left] < self.data[smallest]:
smallest = left
if right < n and self.data[right] < self.data[smallest]:
smallest = right
if smallest == i:
break # これ以上動かないので終了
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
i = smallest
h = MinHeap()
for x in [5, 1, 8, 3, 2]:
h.push(x)
print(h.peek()) # 1
print([h.pop() for _ in range(5)]) # [1, 2, 3, 5, 8]これをmax-heapにしたいときは、比較の向きを反転するだけです。_sift_up と _sift_down の中の < をすべて > に変えれば、根が最大のヒープになります。
計算量 — なぜ build-heap は O(n) で済むのか
ヒープの主な操作の計算量をまとめます。
- peek / find-min:
O(1)（根を見るだけ） - push:
O(log n) - pop:
O(log n) - 任意の要素の探索（search）:
O(n)。ヒープは「根が最小か最大か」しか保証しないので、途中の要素を探すのは苦手です
ここで押さえたいのが、n個の配列から一気にヒープを作るbuild-heap（heapify）です。素朴には「空のヒープにn回pushすればいい」と考えますが、それだと O(n log n) かかります。ノードのおよそ半分が最深段にあり、pushのたびに長い距離を上へ運ぶことになるからです。
ところが、末尾（下の段）から順にsift-downしていくボトムアップ構築（Floyd法）を使うと O(n) で済みます。直感的な理由はこうです。sift-downで各ノードが動く距離は、そのノードの高さに比例します。葉（全体の約半数）は高さ0で仕事はゼロ、上に行くほどノード数は少なくなります。つまり多数派である下の段ほど移動距離が短いので、全体の仕事量が抑えられるのです。数式でも全ノードの高さの総和は O(n) に収まります（Σ h / 2^h が2に収束するため）。
「build-heapは O(n)、n回pushは O(n log n)」——この差は実務でも効いてくるので覚えておくと得です。計算量の記法そのものに不安があれば、先に計算量とBig-O記法 入門を読むと以降の比較がすっと入ってきます。
ヒープソート — その場で O(n log n)
ヒープを使えば、そのまま並べ替えができます。ヒープソート（heapsort）の手順は次の通りです。
- 配列全体を
O(n)でmax-heap化する（build-heap） - 根（最大値）を末尾の要素と交換し、ヒープのサイズを1減らして根をsift-downする
- 2をn回繰り返すと、配列が昇順に並ぶ
各回のsift-downが O(log n) で、それをn回行うので全体は O(n log n) です。最悪・平均・最良のいずれも O(n log n) で安定していて、追加メモリが O(1) のin-place（その場）ソートである点が長所です。一方で安定ソートではありません（同じ値の相対順序が保たれない）。
Pythonの heapq（後述、min-heap）を使うと、簡易版は次のように書けます。ただしこれは元の配列とは別に配列を持つため、教科書的なin-place版とは別物である点に注意してください。
import heapq
def heapsort(a):
heap = a[:] # コピーを取る（この簡易版は in-place ではない）
heapq.heapify(heap) # O(n) でヒープ化
return [heapq.heappop(heap) for _ in range(len(heap))] # 各 pop が O(log n)
print(heapsort([5, 1, 8, 3, 2])) # [1, 2, 3, 5, 8]他の並べ替え手法との比較はソートアルゴリズム入門にまとめています。
各言語の標準ライブラリ（表）
主要言語のヒープ／優先度付きキューは、デフォルトがmin-heapかmax-heapかで作法が分かれます。2026年時点の一次ソースをもとに整理すると次の通りです。
| 言語 / ライブラリ | デフォルト | min / max の切り替え | 主な計算量 |
|---|---|---|---|
Python heapq | min-heap | 符号を反転、または Python 3.14+ の max 系関数 | push / pop が O(log n)、heapify が O(n) |
Java PriorityQueue | min-heap（自然順序） | Comparator.reverseOrder() を渡す | offer / poll が O(log n)、peek が O(1) |
C++ std::priority_queue | max-heap | 第3テンプレート引数に std::greater | push / pop が O(log n)、top が O(1) |
Go container/heap | min-heap ベース | 自作の Less の向きで決める | push / pop が O(log n) |
Rust BinaryHeap | max-heap | 要素を std::cmp::Reverse で包む | push / pop が O(log n)、peek が O(1) |
| JavaScript | 標準なし（2026年時点） | ライブラリか自作で対応 | 実装依存 |
Pythonの heapq はヒープ本体がただの list で、専用のクラスを作りません。基本操作は次の通りです。
import heapq
# heapq はただの list を min-heap として扱う
tasks = []
heapq.heappush(tasks, (2, "レビュー対応"))
heapq.heappush(tasks, (1, "本番障害の調査"))
heapq.heappush(tasks, (3, "議事録の清書"))
# 優先度（タプルの第1要素）が小さいものから取り出される
while tasks:
priority, name = heapq.heappop(tasks)
print(priority, name)
# 1 本番障害の調査
# 2 レビュー対応
# 3 議事録の清書
# 既存のリストをまとめてヒープ化（線形時間 O(n)）
nums = [5, 1, 8, 3, 2]
heapq.heapify(nums)
print(nums[0]) # 1 （根が最小）
# 大きい順トップ2は nlargest が手軽
print(heapq.nlargest(2, [5, 1, 8, 3, 2])) # [8, 5]
# max-heap が欲しいときは符号を反転して入れる（Python 3.13 以前の定番）
max_heap = []
for x in [5, 1, 8, 3, 2]:
heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap)) # 8heapq はmin-heap専用で、Python 3.14でmax-heap用の関数（heappush_max など）が追加されましたが、それ以前は符号反転が定番でした。なお heapq はスレッドセーフではないため、複数スレッドで共有するなら queue.PriorityQueue を使います。
JavaやC++、Go、Rustにはそれぞれ標準のヒープがある一方、JavaScriptには2026年時点で標準の優先度付きキューやヒープが存在しません。正式なTC39提案（Stage 1以上）も確認できず、将来入るかは未確認です。実務ではnpmライブラリか自作で対応します。
実務での使いどころ（Dijkstra・ハフマン・Top-K・中央値）
優先度付きキューは「次に処理すべき1件」を選ぶ場面で幅広く登場します。
- Dijkstra法の最短経路: まだ確定していない頂点のうち、距離が最小のものを取り出すのに使います（min優先度付きキュー）。二分ヒープ版の計算量は
O((V+E) log V)です。詳しくはグラフ探索アルゴリズム入門を参照してください。A*探索も同じ枠組みです - ハフマン符号化: 頻度が最小の2つのノードを繰り返し結合していく処理でmin-heapを使います（データ圧縮の基礎入門で扱っています）
- イベント駆動シミュレーション: 「次に起こる＝時刻が最小」のイベントを取り出すのに使います
- タスクスケジューラ／ジョブの優先度管理: 優先度が高いものから処理します
- K個のソート済みリストのマージ: 各リストの先頭をヒープに入れて最小を取り出すと
O(N log k)でマージできます
理論の補足として、フィボナッチヒープを使うとdecrease-keyが償却 O(1) になり、Dijkstraを O(E + V log V) に改善できます（二項ヒープのdecrease-keyは O(log n)）。ただし定数が大きく実装も複雑なため、実務では二分ヒープと後述の遅延削除を組み合わせた方が速いことが多いです。
代表的な応用として、上位k件を求めるTop-Kを見ておきます。全部をソートせず、サイズkのmin-heapを保つのがコツで、計算量は O(n log k) です。
import heapq
def top_k_largest(nums, k):
heap = [] # サイズ k の min-heap を保つ
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]: # 現在の最小より大きければ入れ替える
heapq.heapreplace(heap, x) # pop してから push、O(log k)
return sorted(heap, reverse=True)
print(top_k_largest([5, 1, 8, 3, 9, 2, 7], 3)) # [9, 8, 7]もう一つの定番が、データを流し込みながら中央値を追う2ヒープ法です。下位半分をmax-heap、上位半分をmin-heapに持ち、両者のサイズ差を1以内に保つと、更新が O(log n)、中央値の取得が O(1) になります。
よくある落とし穴
ヒープを使うときに詰まりやすい点を挙げておきます。
- heapqはmin-heap固定: 最大を取りたいなら符号反転か、Python 3.14以降の
heappop_maxなどを使います - タプルの同点比較エラー（Python）:
(priority, item)で優先度が同点だと第2要素itemを比較します。itemが比較不能（dictなど）だとTypeErrorで落ちます。対策は、単調増加カウンタを挟んで(priority, counter, item)の3要素にするか、@dataclass(order=True)で優先度以外をfield(compare=False)にする方法です - decrease-keyが標準ヒープに無い: 定石は遅延削除（lazy deletion）です。古いエントリは消さず、新しい優先度で再挿入し、pop時に無効なエントリをスキップします。
heapqでDijkstraを書くときの定番イディオムです（Goはheap.Fix/heap.Removeで更新できます） - 非スレッドセーフ:
heapq、JavaのPriorityQueue、C++、Go、Rustのヒープはいずれも並行アクセスを想定していません。並行用途ではPythonのqueue.PriorityQueueやJavaのPriorityBlockingQueueを使います - ヒープはソート済みではない: 根以外の順序は保証されません。並べ替えたいならpopを繰り返します（それがヒープソートです）
- build-heapの誤解: n回pushは
O(n log n)です。O(n)にしたいならheapify/make_heapを使います
同じアルゴリズム入門シリーズの動的計画法（DP）入門や二分探索入門と合わせて読むと、データ構造とアルゴリズムの引き出しが広がります。
まとめ
- 優先度付きキューは「操作の約束事」を定めた抽象データ型で、二分ヒープはその最も一般的な実装（両者はイコールではない）
- 二分ヒープは完全二分木を配列で表し、親は
(i-1)//2、子は2*i+1と2*i+2でたどれる（0-indexed） - push（sift-up）とpop（sift-down）は
O(log n)、peekはO(1)。要素の探索はO(n)で苦手 - build-heapはボトムアップ構築なら
O(n)。多数派の下の段ほど移動距離が短いのが理由。n回pushのO(n log n)とは別物 - ヒープソートは
O(n log n)・in-placeだが安定ではない。Dijkstra・ハフマン・Top-K・中央値の2ヒープ法など応用は幅広い
まずは配列の親子インデックスと、sift-up / sift-downの2つの玉突きを手でトレースしてみてください。この2つが腑に落ちれば、ヒープはとても素直なデータ構造だと感じられるはずです。
