- pythonでの優先度付きキューの実装方法
- Listとheapqの違い
優先度付きキューの実装方法
pythonでは、優先度付きキューのデータ構造は標準ライブラリheapqで実装することができます。
優先度付きキューの実装を解説していきます。
まずは、heapify関数にlistを渡すことで初期化します。
import heapq
# heapの作成
my_heap = [5, 3, 1, 4, 2]
heapq.heapify(my_heap)
print(my_heap)[1, 2, 5, 4, 3]
heappushを使って、キューに要素を追加していきます。
# heapへの要素の追加
heapq.heappush(my_heap, 10)
print(my_heap)[1, 2, 5, 4, 3, 10]
heappopを使うと優先度の高い(値の小さい)要素から取り出すことができます。
# heapからの要素の取り出し
tmp = heapq.heappop(my_heap)
print(tmp)
print(my_heap)1
[2, 3, 5, 4, 10]
dequeの応用的な操作
タプルを扱う
優先度付きキューの要素には、タプルを追加することもできます。
その場合、タプルの第1要素が優先度の値となります。
my_heap = [(5, 'O'), (3, 'L'), (1, 'H'), (4, 'L'), (2, 'E')]
heapq.heapify(my_heap)
print(my_heap)
for i in range(len(my_heap)):
tmp = heapq.heappop(my_heap)
print(tmp[1])[(1, 'H'), (2, 'E'), (5, 'O'), (4, 'L'), (3, 'L')]
H
E
L
L
O
逆順で要素を取り出す
標準機能ではありませんが、優先度の低い(値の大きい)要素から順に取り出してみます。
Listの要素をすべて反転してから、heapに変更しています。
# heapの作成
my_heap = [5, 3, 1, 4, 2]
# 要素に-1をかけてからheapにする
for i in range(len(my_heap)):
my_heap[i] *= -1
heapq.heapify(my_heap)
# 要素を取り出すときに-1をかけて元に戻す
tmp = heapq.heappop(my_heap) * -1
print(tmp)5
heapとListの違い
heapqと同じことをListのmin関数を使うことで実装できますが、heapqのほうが高効率となっています。
Listでmin関数を使用するとO(n)の計算量になりますが、heapのアルゴリズムではO(log(n))で済みます。
そのため、優先度付きのキューを使う場合はheapqを使うことが望ましいです。
優先度付きキューの関連ライブラリ
優先度付きキューを実装するライブラリはheapq以外にもqueue.PriorityQueueライブラリが存在します。
heapqとqueue.PriorityQueueは、両方とも優先度付きキューを扱うためのものですが、2点違いがあります。
スレッドセーフ性
スレッドセーフ性は、優先度付きキューが複数のスレッドからの操作に対応しているかどうかの違いです。
heapqはスレッドセーフではなく、複数のスレッドから同時にアクセスすると競合状態が発生する可能性があります。
一方で、queue.PriorityQueueはスレッドセーフなので、複数のスレッドから同時にアクセスしても安全です。
これはthreadingモジュールを用いたマルチスレッドプログラミングに適しています。
実装について
実装上の違いもあります。
heapqは、通常のListをヒープキューとして操作するための関数を提供しています。
Listをヒープとして扱うため、追加や削除の際にリストの全体が再構築される可能性があります。
queue.PriorityQueueは、queueモジュールに組み込まれたクラスで、ヒープキューの抽象化された実装を提供しています。
内部的にはリストやheapqモジュールを使用している可能性がありますが、プログラマはその詳細を気にせずに利用できます。
参考文献
コメント