Pythonでプライオリティキューを実装する方法（コード付き）

この記事では、Python での優先キューの実装方法 (コード付き) について説明します。一定の参考値があり、困っている友人は参照してください。お役に立てれば幸いです。

#1. 要件指定された優先度で要素を並べ替え、各ポップ操作で最も高い優先度を返すキューを実装したいと考えています。 #2. 解決策

heapq モジュールを使用して実装するコード:

import heapq

#利用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)

if __name__ == '__main__':
    q=PriorityQueue()
    q.push(Item('foo'),1)
    q.push(Item('bar'),5)
    q.push(Item('spam'),4)
    q.push(Item('grok'),1)

    print(q.pop())
    print(q.pop())
    #具有相同优先级的两个元素，返回的顺序同它们插入到队列时的顺序相同
    print(q.pop())
    print(q.pop())

実行結果:

Item('bar')
Item('spam')
Item('foo')
Item('grok')

上記のコードの中核は、heapq モジュールの使用にあります。関数 heapq.heapqpush() と heapq.heapqpop() は、リスト _queue への要素の挿入と削除をそれぞれ実装し、リストの最初の要素の優先順位が最低になるようにします。 heappop() メソッドは常に [最小の] 要素を返すため、これがキューから正しい要素をポップするための鍵となります。さらに、プッシュおよびポップ操作の複雑さは O(logN) (N はヒープ内の要素の数を表します) であるため、N の値が大きくても、これらの操作の効率は非常に高くなります。 上記のコードでは、キューはタプル (-priority、index、item) で構成されています。優先順位に負の値を指定するのは、キューを要素の優先順位の高いものから低いものへの順序で配置できるようにするためです。

変数インデックスの機能は、同じ優先順位を持つ要素を適切な順序で配置することです。増加し続けるインデックスを維持することにより、要素はキュー内に表示される順序で配置されます。インデックスの役割を説明するには、次の例を見てください:

コード:

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    a=(1,Item('foo'))
    b=(5,Item('bar'))
    #下面一句打印True
    print(a<b)


    c=(1,Item('grok'))
    #下面一句会报错：TypeError: '<' not supported between instances of 'Item' and 'Item'
    print(c<a)


    d=(1,0,Item('foo'))
    e=(5,1,Item('bar'))
    f=(1,2,Item('grok'))
    #下面一句打印True
    print(d<e)
    #下面一句打印True
    print(d<f)

以上がPythonでプライオリティキューを実装する方法（コード付き）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。