本文實例講述了Python實現優先級隊列的方法。分享給大家供大家參考，具體如下：
問題：要實現一個隊列，它能夠以給定的優先級對元素排序，且每次pop操作時都會返回優先級最高的那個元素；
解決方案：采用heapq模塊實現一個簡單的優先級隊列
# example.py
#
# Example of a priority queue
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]
# Example use
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)
print("Should be bar:", q.pop())
print("Should be spam:", q.pop())
print("Should be foo:", q.pop())
print("Should be grok:", q.pop())
Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
Should be bar: Item('bar')
Should be spam: Item('spam')
Should be foo: Item('foo')
Should be grok: Item('grok')
>>>
可以看出：第一次執行pop()操作時返回的元素具有最高的優先級；對于相同優先級的兩個元素（foo和gork）返回的順序同它們插入到隊列時的順序相同。
在這段代碼中，隊列以元組(-priority, self._index, item)的形式組成，priority取負值是為了隊列按照從高到低的順序排列，這和堆默認的從小到大的排序相反。
變量index的作用是對相同優先級的元素以適當的順序排列，特別對同優先級的元素間做比較操作時扮演了重要的角色。
Item實例無法進行次序比較：
a=Item('foo')
b=Item('bar')
print('a<b: ',a<b)
>>>
Traceback (most recent call last):
File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py", line 27, in <module>
print('a<b: ',a<b)
TypeError: unorderable types: Item() < Item()
>>>
如果以元組(priority, item)的形式來表示元素，只要優先級不同，就可進行比較：
a=(1,Item('foo'))
b=(5,Item('bar'))
c=(1,Item('gork'))
print('a<b: ',a<b)
print('a<c: ',a<c)
>>>
a<b: True
Traceback (most recent call last):
File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py", line 29, in <module>
print('a<c: ',a<c)
TypeError: unorderable types: Item() < Item()
>>>
引入額外的索引值，以(priority, index, item)的方式建立元組，就可以避免相同優先級無法比較的問題，因為沒有哪兩個元組會有相同的index值；
a=(1,0,Item('foo'))
b=(5,1,Item('bar'))
c=(1,2,Item('gork'))
print('a<b: ',a<b)
print('a<c: ',a<c)
>>>
a<b: True
a<c: True
>>>
如果想將這個隊列用于線程間通信，還需要增加適當的鎖和信號機制。
（代碼摘自《Python Cookbook》）
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
