Pythonのヒープキュー（heapq）とは？基本の使い方をわかりやすく解説

ヒープキュー（ヒープ）とは、各親ノードがその子ノードと同じかそれより小さい値を持つという特殊な木構造のことです。Pythonでは、標準ライブラリのheapqモジュールを使って簡単に扱うことができます。ヒープキューは、優先度の高い項目を先に処理できる「優先度付きキュー」の実装に非常に役立ちます。

ヒープ操作のための主な関数

ヒープキューは、Pythonの組み込みライブラリheapqを使って作成・操作します。このライブラリには、ヒープデータ構造に対するさまざまな操作を行うための関数が用意されています。主な関数は以下の通りです。

• heapify − 通常のリストをヒープに変換します。変換後は最小の要素がインデックス0に移動しますが、それ以外の要素は必ずしもソートされません。
• heappush − 既存のヒープ構造を壊さずに新しい要素を追加します。
• heappop − ヒープから最小の要素を取り出して返します。
• heapreplace − ヒープ内の最小要素を削除し、引数で指定した新しい値を挿入します。

ヒープの作成方法

ヒープは、要素の入ったリストに対してheapify関数を呼び出すだけで簡単に作成できます。以下の例では、リストを渡すとheapify関数が要素を並べ替え、最小の要素が先頭に移動します。

コード例

import heapq

H = [21, 1, 45, 78, 3, 5]
# heapifyで要素を並べ替える
heapq.heapify(H)
print(H)

実行結果

[1, 3, 5, 78, 21, 45]

ヒープへの要素の挿入

ヒープに要素を追加するにはheappush関数を使用します。新しく追加された要素は、ヒープの条件（親が子以下であること）が保たれるように自動的に適切な位置へ移動されるため、手動でheapifyを呼び出す必要はありません。以下の例では、数値8を挿入しています。

コード例

import heapq

H = [21, 1, 45, 78, 3, 5]
# リストをヒープに変換
heapq.heapify(H)
print(H)
# 要素を追加
heapq.heappush(H, 8)
print(H)

実行結果

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

ヒープからの要素の削除

heappop関数を使うと、ヒープの先頭にある最小の要素を取り除くことができます。以下の例では、最小値である1が取り除かれ、残りの要素がヒープ条件を満たすように自動的に並べ替えられます。

コード例

import heapq

H = [21, 1, 45, 78, 3, 5]
# ヒープを作成
heapq.heapify(H)
print(H)

# 最小の要素を取り除く
heapq.heappop(H)

print(H)

実行結果

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

ヒープ内の要素の置き換え

heapreplace関数は、常にヒープ内の最小要素を削除し、新しい要素を挿入します。挿入位置はあらかじめ決まっているわけではなく、ヒープの条件を満たすように自動的に決定されます。既存の最小値を別の値に置き換えたい場合に便利な関数です。

コード例

import heapq

H = [21, 1, 45, 78, 3, 5]
# ヒープを作成
heapq.heapify(H)
print(H)

# 最小の要素を6に置き換える
heapq.heapreplace(H, 6)
print(H)

実行結果

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]

まとめ

heapqモジュールを使えば、リストベースの軽量なヒープ（優先度付きキュー）を簡単に実装できます。最小値の取得や挿入・削除がすべてO(log n)で行えるため、タスクスケジューリングやダイクストラ法などのアルゴリズムでも広く活用されています。