Overview
ヒープ（Heap） は、最小値または最大値を効率的に管理できるデータ構造 であり、優先度付きキュー（Priority Queue） を実現するために使われる。
Python では heapq モジュールを使うと、最小ヒープ（Min-Heap）を簡単に実装 できる。
1.ヒープの基本
2.最大ヒープ（Max-Heap）の実装
3.ヒープの応用
4.典型問題を解いてみる
1. ヒープの基本
(1) ヒープとは？
-
最小ヒープ（Min-Heap）: 常に最小の要素が
heap[0]に保持される -
最大ヒープ（Max-Heap）: 常に最大の要素が
heap[0]に保持される -
ヒープは「完全二分木（Complete Binary Tree）」
二分木（Binary Tree）: 各ノードが 最大2つの子 を持つ木
完全二分木（Complete Binary Tree）:左から順に詰めて ノードを配置する
最下段以外はすべて埋まっている
最小値（または最大値）がルート（頂点）に来る
親ノードの値は子ノードの値より小さい（または大きい）
例: 最小ヒープ（Min-Heap）の木構造1 / \ 3 4 / \ / 7 6 5 -
優先度付きキューを実現するために使用される
(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）
print(heapq.heappop(heap)) # 1 最小値を取得しながら削除
print(heap) # [3, 4]
- リストとは異なり、順番が保証されるのは最小値のみ
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
- 負の値を入れることで、最大値が heap[0] に来る
-
heapq.heappop()の戻り値に -1 をかけると、元の正の値を取得できる
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）
(2) N 個の要素の中から K 個の最大値を求める
import heapq
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(heapq.nlargest(k, arr)) # [20, 15, 10]
-
heapq.nlargest(k, arr)を使うと、最大 K 個の要素を O(K log N) で取得
(3) 2つの最小値を合成する（最小コストで作る）
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) # 最小合成コスト
- 貪欲法（Greedy Algorithm）を用いた最小コスト合成アルゴリズム
- ロジックの動作手順
-
# 例として、以下のリストを考えます： A = [1, 2, 3, 4, 5] # ステップ 1: 初期状態 heapq.heapify(A) # 最小ヒープに変換：[1, 2, 3, 4, 5] （最小値が先頭） # ステップ２〜５はwhile内の処理 # ステップ 2: 2つの最小値を合成 # 1. 最小値 1 を取り出す # 2. 次に小さい 2 を取り出す # 3. 1 + 2 = 3 を合成コストに加算（現在の合成コスト: 3） # 4. 3 をヒープに戻す # ヒープ: [3, 3, 5, 4] # ステップ 3: 2つの最小値を合成 # 1. 3 を取り出す # 2. 3 を取り出す # 3. 3 + 3 = 6 を合成コストに加算（合計: 3 + 6 = 9） # 4. 6 をヒープに戻す # ヒープ: [4, 5, 6] # ステップ 4: 2つの最小値を合成 # 1. 4 を取り出す # 2. 5 を取り出す # 3. 4 + 5 = 9 を合成コストに加算（合計: 9 + 9 = 18） # 4. 9 をヒープに戻す # ヒープ: [6, 9] # ステップ 5: 最後の 2 つを合成 # 1. 6 を取り出す # 2. 9 を取り出す # 3. 6 + 9 = 15 を合成コストに加算（合計: 18 + 15 = 33） # ヒープ: []（すべて合成完了） # 最終的な合成コスト: 33
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 個の最大値を求めよ。
回答
import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))
print(*heapq.nlargest(K, A))
例題3. 優先度付きキューのシミュレーション
問題: N 個のクエリが与えられる。insert x で x を追加し、pop で最小値を取り出せ。
回答
import heapq
N = int(input())
heap = []
for _ in range(N):
query = input().split()
if query[0] == "insert":
heapq.heappush(heap, int(query[1]))
elif query[0] == "pop":
print(heapq.heappop(heap))
例題4. 2つの最小値を合成する
問題: N 個の数を最小コストで合成せよ。
回答
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)