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関数はヒープの性質を自動的に維持するため、追加された要素が最小値であれば先頭へ、そうでなければ適切な位置へ配置されます。以下の例では、数値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関数を使うと、ヒープの先頭にある最小の要素を取り除くことができます。以下の例では、この関数を呼び出すたびに常に最小値の要素が削除されます。

例

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)
# 要素を置き換える
heapq.heapreplace(H,6)
print(H)

実行結果

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