PythonでPriorityQueue

PythonでPriorityQueueを使おうと思ったら割と微妙な感じだったので書いてみる。
PriorityQueueとは優先順キューのこと。（優先順位にしたがって要素が追加削除できるキュー
ヒープアルゴリズムによって制御されており、
最小値を得ながら要素を追加していきたい、
なんていうときに使う。
どうしてこれが有用かというと、探索ルーチンなどのような場合に、
現在最小（最優先のもの）を探しながら見つかった要素をQueueに溜め込む、
なんていうときに単純なlistでは効率的にできないのだが、
これを解決する。
毎回ソートしたり、適切な場所に挿入するようなappendを書くよりずっと良い。

これには用意されているモジュールheapqを使う。
関数化されているので、heappushとheappopでデータを操作する簡易クラスを定義してみた。

from heapq import heappush, heappop
from random import randint
from time import time

class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def __len__(self):
        return len(self.queue)
    def __contains__(self, item):
        return item in self.queue
    #...

class Foo(object):
    def __init__(self, index, value):
        self.index = index
        self.value = value
    def __str__(self):
        return "Foo%02d(%d)" % (self.index, self.value)
    def __le__(self, other):
        return self.value <= other.value

queue = PriorityQueue()

data = [1,3,5,7,9,2,100,104,1000,2000,999,999,999,0,45]
for index, value in enumerate(data):
    queue.push(Foo(index, value))
    
while len(queue) > 0:
    foo = queue.pop()
    print foo

大小判定に__le__が使われているようなので要素に対する__le__を定義してある。

結果はこんな感じ。

Foo13(0)
Foo00(1)
Foo05(2)
Foo01(3)
Foo02(5)
Foo03(7)
Foo04(9)
Foo14(45)
Foo06(100)
Foo07(104)
Foo11(999)
Foo10(999)
Foo12(999)
Foo08(1000)
Foo09(2000)

popする際に適切な並びになっていることがわかる。
ただし、heapに使っているlistが常にソートされているわけではないことに注意。
あくまでpushやpopの際に適切な挿入や削除を行ってくれるだけ。
これだけで単にlistに挿入やソート済みlistを使うより何十倍も速くなる。
検証プログラムは時間があれば。