Python優先キュー構造を実現する方法詳細

最も簡単な実現
一つの列は少なくとも2つの方法、putとgetを満たします。
最小の山を借りて実現する。
ここでは「値が大きいほど優先度が高い」という順に。

#coding=utf-8 
from heapq import heappush, heappop 
class PriorityQueue: 
  def __init__(self): 
    self._queue = [] 
 
  def put(self, item, priority): 
    heappush(self._queue, (-priority, item)) 
 
  def get(self): 
    return heappop(self._queue)[-1] 
 
q = PriorityQueue() 
q.put('world', 1) 
q.put('hello', 2) 
print q.get() 
print q.get() 

 heappqモジュールを使用して実現します。
以下のクラスは、heappqモジュールを利用して、簡単な優先順位の列を実現する。

import heapq

class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0

  def push(self, item, priority):
    heapq.heappush(self._queue, (-priority, self._index, item))
    self._index += 1

  def pop(self):
    return heapq.heappop(self._queue)[-1]

以下はその使い方です。

>>> class Item:
...   def __init__(self, name):
...     self.name = name
...   def __repr__(self):
...     return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>

注意深く観察すると、最初のpop（）動作は優先度が最も高い要素に戻ることが分かった。また、同じ優先度の要素（fooとgrok）が二つある場合、pop動作は、それらが列に挿入された順に戻ることに留意されたい。
 関数heappq.heappsh()とheappq.heappp()はそれぞれ列にあります。queueに最初の要素を挿入して削除し、キュー_queueは、最初の要素が最小優先度を持つことを保証します（1.4節はすでにこの問題を議論しました）。heappp()関数は常に「最小」の要素を返します。これはキューのpop操作が正しい要素に戻ることを保証する鍵です。また、Pushとpopの操作時間の複雑さはO（log N）であるため、Nは山の大きさであるため、Nが大きい場合でも動作速度は速い。
上記のコードでは、キューは一つの(-privisty、index、item)のタプルを含んでいます。優先度が負の値の目的は、優先度の高い元素から低い順に配列させることである。これは、一般的な優先度の低い山から高い山への順序とは正反対である。
index変数の役割は、同じ優先要素の正確な並べ替えを保証することである。増加するindexの下付き変数を保存することにより、要素が挿入された順序で並べ替えられることを確認することができます。また、index変数も同じ優先要素を比較する際に重要な役割を果たす。
これらを明らかにするために、Itemの例は、順序付けをサポートしていないと仮定する。

>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

タプルを使えば、二つの要素の優先度が違うだけで比較できます。しかし、2つの要素の優先度が同じであれば、比較演算は前と同じエラーになります。

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

他のindex変数を導入することで、3つのタプルを構成することができます。上記のエラーは2つの要素が同じindex値を持つことは不可能です。Pythonは元のグループを比較する時、前の比較と結果が確定できます。後の比較操作は発生しません。

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>

複数のスレッドで同じキューを使いたいなら、適切なロックと信号量の仕組みを追加する必要があります。12.3小節の例のデモはどうやって行われているか確認できます。
深く考える
関数heappq.heappsh()とheappq.heappp()はそれぞれ列にあります。queueに最初の要素を挿入して削除し、キュー_queueは、最初の要素が最小優先度を持つことを保証します（1.4節はすでにこの問題を議論しました）。heappp()関数は常に「最小」の要素を返します。これはキューのpop操作が正しい要素に戻ることを保証する鍵です。また、Pushとpopの操作時間の複雑さはO（log N）であるため、Nは山の大きさであるため、Nが大きい場合でも動作速度は速い。
上記のコードでは、キューは一つの(-privisty、index、item)のタプルを含んでいます。優先度が負の値の目的は、優先度の高い元素から低い順に配列させることである。これは、一般的な優先度の低い山から高い山への順序とは正反対である。
index変数の役割は、同じ優先要素の正確な並べ替えを保証することである。増加するindexの下付き変数を保存することにより、要素が挿入された順序で並べ替えられることを確認することができます。また、index変数も同じ優先要素を比較する際に重要な役割を果たす。
これらを明らかにするために、Itemの例は、順序付けをサポートしていないと仮定する。

>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

タプルを使えば、二つの要素の優先度が違うだけで比較できます。しかし、2つの要素の優先度が同じであれば、比較演算は前と同じエラーになります。

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

他のindex変数を導入することで、3つのタプルを構成することができます。上記のエラーは2つの要素が同じindex値を持つことは不可能です。Pythonは元のグループを比較する時、前の比較と結果が確定できます。後の比較操作は発生しません。

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>

複数のスレッドで同じキューを使いたいなら、適切なロックと信号量の仕組みを追加する必要があります。12.3小節の例のデモはどうやって行われているか確認できます。
heappqモジュールの公式文書には、より詳細な例とその実装についての詳細な説明があります。