Overview
ヒープ（Heap） は、最小値または最大値を効率的に取り出すためのデータ構造であり、優先度付きキュー（Priority Queue）を実現するために使われる。
Python では heapq モジュールを使うと、最小ヒープ（Min-Heap）を簡単に実装できる。
1.ヒープの基本
2.最大ヒープ（Max-Heap）の実装
3.ヒープの応用
4.典型問題を解いてみる
1. ヒープの基本
(1) ヒープとは？
ヒープは、次の性質を満たす 完全二分木 である。
- 最小ヒープ（Min-Heap）
- 常に最小の要素が
heap[0]に保持される - 親ノードの値 ≤ 子ノードの値
- 常に最小の要素が
- 最大ヒープ（Max-Heap）
- 常に最大の要素が
heap[0]に保持される - 親ノードの値 ≥ 子ノードの値
- ※Python の heapq は最大ヒープを提供しないため、
最大ヒープを使いたい場合は値を負にするなどして擬似的に実現する
- 常に最大の要素が
ここでいう「完全二分木」は次を意味する：
- 各ノードは最大 2 つの子を持つ（二分木）
- ノードは 左から順に詰めて 配置される
- 最下段以外はすべて埋まっている
最小ヒープのイメージ（配列 [1, 3, 4, 7, 6, 5]）：
1
/ \
3 4
/ \ /
7 6 5
Python の heapq では、この完全二分木を 1 次元配列（リスト）で表現している。
- 親：i
- 左の子：2*i + 1
- 右の子：2*i + 2
という対応になっている。
(2) Python の heapq の基本操作
import heapq
heap = []
# 要素を追加（push）
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heap) # [1, 3, 4]（最小値が先頭にくる）
# 最小値を取得（pop）
x = heapq.heappop(heap) # 1 を取り出しつつ削除
print(x) # 1 最小値を取得しながら削除
print(heap) # [3, 4]
ポイント：
-
heapは単なるリストだが、heapq経由で操作することでヒープとして振る舞う - 常に最小要素だけが保証される（heap 全体がソートされているわけではない）
(3) 主な操作と計算量
| 操作名 | 説明 | 関数 | 計算量 |
|---|---|---|---|
| 追加（push） | 要素をヒープに追加 | heapq.heappush(h, x) |
O(log N) |
| 取り出し（pop） | 最小要素を取り出して削除 | heapq.heappop(h) |
O(log N) |
| 最小値の参照 | 削除せずに最小要素を見る | h[0] |
O(1) |
| 配列をヒープ化 | リストをヒープ構造に変換 | heapq.heapify(h) |
O(N) |
| 最大 K 個・最小 K 個取得 | 上位 K 個の要素を取得 | heapq.nlargest/nsmallest |
O(N log K) |
2. 最大ヒープ（Max-Heap）の実装
Python の heapq は 最小ヒープのみ を提供する。
最大ヒープを使いたい場合は、値にマイナスを掛けて管理するのが定番テクニック。
import heapq
heap = []
# 負の値を追加（最大値を管理）
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
heapq.heappush(heap, -4)
# 最大値を取り出す
print(-heapq.heappop(heap)) # 4
print(-heapq.heappop(heap)) # 3
print(-heapq.heappop(heap)) # 1
ポイント：
-
heapの中では [-4, -1, -3] のように最小値（＝元の値の最大）が先頭に来ている - 取り出すときに マイナスを掛けて元に戻す だけで最大ヒープとして使える
- 「大きいものから順に処理したい」優先度付きキューでよく使うテクニック
3. ヒープの応用
(1) N 個の要素の中から K 番目に小さい要素を求める
import heapq
arr = [7, 10, 4, 3, 20, 15]
k = 3
heapq.heapify(arr) # 配列をヒープ化
for _ in range(k - 1):
heapq.heappop(arr) # k-1 回 pop する
print(heapq.heappop(arr)) # 3番目に小さい値（7）
ポイント：
- 「K 番目に小さい」＝「小さい順に K 回取り出したときの最後の値」
- 計算量はおおよそ O(N + K log N)
(2) N 個の要素の中から K 個の最大値を求める
import heapq
arr = [7, 10, 4, 3, 20, 15]
k = 3
top_k = heapq.nlargest(k, arr)
print(top_k) # [20, 15, 10]
ポイント：
- heapq.nlargest(k, arr) は内部的にヒープを使っている
- 計算量は O(N log K) で、単純ソート（O(N log N)）より効率的なことが多い
(3) 2つの最小値を合成する（最小コストで作る）
典型的な「最小コストで合成」問題（Huffman 木 / ロープを束ねる問題 など）：
import heapq
N = int(input()) # 数列の要素数
A = list(map(int, input().split())) # 数列
heapq.heapify(A) # 配列を最小ヒープに変換
cost = 0 # 合成コストの合計
while len(A) > 1:
x = heapq.heappop(A) # 最小値を取り出す
y = heapq.heappop(A) # 2番目に小さい値を取り出す
cost += x + y # 合成コストを追加
heapq.heappush(A, x + y) # 合成した値をヒープに戻す
print(cost) # 最小合成コスト
ポイント：
- 毎回「最も小さい 2 つ」を合成するのが最適（貪欲法）
- 各ステップで pop 2 回・push 1 回 → 1 回あたり O(log N)
- 全体の計算量は O(N log N)
4. 典型問題を解いてみる
例題1. K 番目に小さい値を求める
問題: N 個の整数列A から K 番目に小さい値を求めよ。
回答
import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(K - 1):
heapq.heappop(A)
print(heapq.heappop(A))
例題2. K 個の最大値を求める
問題: N 個の整数列 A と整数 K が与えられる。最大値から順に K 個 の値を出力せよ。
回答
import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = heapq.nlargest(K, A)
print(*ans)
例題3. 優先度付きキューのシミュレーション
問題: Q 個のクエリが与えられる。クエリは次の 2 種類：
- insert x : x を追加する
- pop : 最小値を 1 つ取り出して出力する
ヒープを使ってこれを実装せよ。
回答
import heapq
import sys
input = sys.stdin.readline
Q = int(input())
heap = []
for _ in range(Q):
query = input().split()
if query[0] == "insert":
x = int(query[1])
heapq.heappush(heap, x)
elif query[0] == "pop":
# この実装では「必ず要素が 1 つ以上ある状態で pop が呼ばれる」前提
x = heapq.heappop(heap)
print(x)
例題4. 2つの最小値を合成する
問題:
N 個の正の整数 A が与えられる。
以下の操作を、配列の要素が 1 個になるまで繰り返す：
- 配列から最小の 2 つの値 x, y を取り出す
- コストに (x + y) を加算する
- (x + y) を配列に追加する
最終的な 合計コスト を求めよ。
回答
import heapq
N = int(input())
A = list(map(int, input().split()))
heapq.heapify(A)
cost = 0
while len(A) > 1:
x = heapq.heappop(A)
y = heapq.heappop(A)
cost += x + y
heapq.heappush(A, x + y)
print(cost)