Pythonのヒープキューアルゴリズム（heapqモジュール）徹底解説

ヒープデータ構造は、優先度付きキュー（プライオリティキュー）を実装するために利用できます。Pythonでは標準ライブラリの heapq モジュールとして提供されており、このモジュールは最小ヒープ（min-heap）を構築します。つまり、値が小さいほど優先度が高いとみなされ、新しい要素を挿入するたびに、ヒープ構造が自動的に再構成されます。

heapqモジュールを使用するには、まずインポートします。

import heapq

heapqモジュールには、以下のようなヒープ操作用のメソッドが用意されています。

heapq.heapify(iterable)

イテラブルなデータセットをヒープ構造に変換します。リストをその場で（in-placeで）ヒープ化します。

heapq.heappush(heap, element)

指定した要素をヒープに挿入し、挿入後にヒープ全体の構造を維持するよう再構成します。

heapq.heappop(heap)

ヒープの先頭（最小値）にある要素を返すと同時に削除し、残りの要素に対して再度ヒープ化を行います。

heapq.heappushpop(heap, element)

要素の挿入と取り出しを1つの処理で実行します。まず要素をプッシュし、その後ヒープの最小要素をポップします。

heapq.heapreplace(heap, element)

こちらも挿入と取り出しを1つの処理で行います。ただし heappushpop とは動作順序が異なり、まずルート（最小要素）を削除してから、新しい要素をヒープに挿入します。

heapq.nlargest(n, iterable, key=None)

データセットから最大の n 個の要素を、大きい順（降順）のリストとして返します。

heapq.nsmallest(n, iterable, key=None)

データセットから最小の n 個の要素を、小さい順（昇順）のリストとして返します。

サンプルコード

import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
heapq.heapify(my_list)
print(my_list)
heapq.heappush(my_list, 7)
print(my_list)
print('Popped Element: ' + str(heapq.heappop(my_list)))
print(my_list)
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)

実行結果

[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19]
Popped Element: 7
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[89, 65, 58, 41]

この例では、まず heapify() でリストをヒープ化し、続いて heappush() で値 7 を挿入しています。その後 heappop() を呼び出すと、ヒープの先頭にある最小値 7 が取り出されます。最後に nlargest(4, ...) を使うことで、リスト内の大きい方から4つの要素が降順で取得できていることが確認できます。このように heapq を使えば、優先度付きキューや「上位N件の抽出」などを効率的に実装できます。