python - Python プライオリティ キューの作成

Question

Python で優先度キューを作成したいと思います。このキューには、優先度番号を持つさまざまな辞書が含まれています。したがって、「get 関数」が呼び出されると、優先度が最も高い (最小の番号) を持つ辞書がキューから取り出され、「関数の追加」が呼び出されると、新しい辞書がキューに追加され、それに基づいて並べ替えられます。優先番号。

助けてください...

前もって感謝します！

Answer 1

標準ライブラリの heapq モジュールを使用します。

優先度を辞書に関連付ける方法は指定しませんが、簡単な実装を次に示します。

import heapq

class MyPriQueue(object):
    def __init__(self):
        self.heap = []

    def add(self, d, pri):
        heapq.heappush(self.heap, (pri, d))

    def get(self):
        pri, d = heapq.heappop(self.heap)
        return d

Answer 2

これは、私のパターン トークのいくつかで、補足として私が通常提示するものです。

class PriorityQueue(object):
 def __init__(self, key=lambda x: x):
   self.l = []
   self.key = key
 def __len__(self):
   return len(self.l)
 def push(self, obj):
   heapq.heappush(self.l, (self.key(obj), obj))
 def pop(self):
   return heapq.heappop(self.l)[-1]

OPの要件は、インスタンス化するときに引数operator.itemgetter('priority')として使用するようです（もちろん、モジュールの先頭に必要です;-）。keyPriorityQueueimport operator

Answer 3

これを行うには、dict オブジェクトをクラスに追加し、内部で検索します。