問題描述
怎樣實作一個按優先級排序的佇列？并且每次pop操作總是回傳優先級最高的那個元素？
解決方案
下面利用heapq模塊實作了一個簡單的優先級佇列類：
import heapq
class PriorityQueue:
"""
簡單的優先級佇列類
"""
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority: int):
"""
在佇列中加入新的值，并保持堆的不變性（即保持最小堆）
:param item: 要加入的值
:param priority: 優先級
:return: None
"""
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
"""
彈出self._queue[0][-1]，即優先級最高的元素的值
:return: item
"""
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('happy'), 1)
q.push(Item('good'), 5)
q.push(Item('beautiful'), 3)
q.push(Item('nice'), 1)
for i in range(0, 4):
print(q.pop())
"""
輸出結果：
Item('good')
Item('beautiful')
Item('happy')
Item('nice')
"""
討論
這里的底層實作是堆排序，函式heapq.heapqpush()和heapq.heappop()分別在佇列_queue上插入和洗掉第一個元素，并且因為_queue是最小堆，所以-priority最小的元組總是排在第一個，這樣就實作了按優先級回傳元素，
在上面的代碼中，佇列中的每個元素是一個元組(-priority, index, item)，元組的大小比較是從第一個元素開始比較，比較結果即為元組比較結果，如相等則依次向后比較，index變數的作用是保證同優先級的元素按照它們的插入順序排序和比較，
我們設定Item實體是不支持排序的：
a = Item('happy')
b = Item('good')
a < b
"""
運行結果：
TypeError: '<' not supported between instances of 'Item' and 'Item'
"""
如果使用元組(-priority, item)，那么當優先級相同時，就會出現如上的運行錯誤，
通過引入另外的index變陣列成三元組(-priority, index, item)，就能很好的避免此錯誤，因為不可能有相同的index值，
關于heapq模塊的更多詳細說明可以參考官方檔案
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/385253.html
標籤：Python