今日の記事では、Python heapq モジュールの使用について見ていきます。
このモジュールは、あなたのアプリケーションのためにあらゆるタイプの優先キューを構築するための迅速かつ容易な方法を提供します。
このモジュールについてもっと理解するために、もう少し詳しく見てみましょう。
Min-Heap としての優先度キュー
優先度キューは、要素に優先度と呼ばれる別のパラメータを持つキューです。
要素の優先度に基づいて、それらの要素が最初にキューからプッシュ/ポップされます。
このモジュールでは、バイナリ・ミニヒープを利用して、優先度キューを構築している。
このヒープキュー・データ構造の主な特性は、最も小さい要素が常に最初にポップオフされることです。
また、どの要素も一度プッシュ／ポップされると、同じような構造が維持されます。
このデータ構造には、ソートなど多くの応用があります。
それでは、このモジュールの使い方を理解しましょう。
この記事もチェック：PythonでのMinヒープデータ構造の実装方法を解説する
Python heapq モジュールを理解する
このモジュールは標準ライブラリの一部なので、pipを使って別途インストールする必要はありません。
heapq モジュールをインポートするには、以下のようにします。
import heapq |
heapq` モジュールでは、優先キューを構築・操作するために必要な3つのメソッドを主に必要としています。
-
heappush(heap, item)->itemをheapにプッシュし、min-heap プロパティを維持します。 -
heappop(heap)-> ヒープから最小のアイテムをポップして返します。ヒープが空の場合、IndexError例外が発生します。 -
heapify(iterable)-> イテレート可能なファイル（リストなど）を最小ヒープに変換します。これは、イテラブルをインプレースで変更します。
通常の整数のリストから優先度キューを構築する簡単な例を見てみましょう。
import heapq
a = [1, 4, 3, 5, 2]
print("List =", a)
# Convert the iterable (list) into a min-heap in-placeheapq.heapify(a)print("Min Heap =", a)
|
結果は以下の通りです。
List = [1, 4, 3, 5, 2]
Min Heap = [1, 2, 3, 5, 4]
|
見ての通り、heapify() メソッドはリストをインプレースで変更し、ミニヒープに変換しています。
なぜミニヒープなのかを観察するために、単純に両方のリストの木表現を描いてみましょう。
import heapq
a = [1, 4, 3, 5, 2]
print("List =", a)
# Convert the iterable (list) into a min-heap in-placeheapq.heapify(a)print("Min Heap =", a)
# Use heappushheapq.heappush(a, 10)
print("After heappush(), Min Heap =", a)
# Use array indexing to get the smallest elementprint(f"Smallest element in the heap queue = {a[0]}")
# Use heappop() and return the popped elementpopped_element = heapq.heappop(a)
print(f"Popped element = {popped_element}, Min Heap = {a}")
|
リストからのミニヒープ表現では、インデックス i を持つノードに対して、その子はインデックス 2*i と 2*i+1 を持つ。
ミニヒープでは、親は子ノードよりも小さい必要があります。
List = [1, 4, 3, 5, 2]
Min Heap = [1, 2, 3, 5, 4]
After heappush(), Min Heap = [1, 2, 3, 5, 4, 10]
Smallest element in the heap queue = 1
Popped element = 1, Min Heap = [2, 4, 3, 5, 10]
|
見てわかるように、2番目のリストは本当にミニヒープの性質に従っています。
このように、heapify() メソッドが正しいミニヒープを与えてくれることが確認されました。
それでは、ヒープにプッシュしたり、ヒープからポップしたりしましょう。
import heapq
def heapsort(iterable):
h = []
for value in iterable:
# Push the elements onto the heap
heapq.heappush(h, value)
# Keep popping the smallest elements and appending them to our sorted list
return [heapq.heappop(h) for i in range(len(h))]
sorted_list = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(sorted_list)
|
結果は以下の通りです。
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
見ての通り、このヒープキューでは簡単に目的の操作を実行することができました! では、このミニヒープを使ってヒープソートでリストをソートしてみましょう。
結果は以下の通りです。
素晴らしい! ヒープキューのプロパティを使ってリストをソートすることができました。
まとめ
この記事では、Python heapq モジュールの使用について学び、順序なしリストをソートするために min-heap プロパティを使用する方法を見てきました。
参考文献
- heapq モジュールに関する Python ドキュメント