本文實(shí)例講述了Python實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法。分享給大家供大家參考，具體如下：
問(wèn)題：要實(shí)現(xiàn)一個(gè)隊(duì)列，它能夠以給定的優(yōu)先級(jí)對(duì)元素排序，且每次pop操作時(shí)都會(huì)返回優(yōu)先級(jí)最高的那個(gè)元素；
解決方案：采用heapq模塊實(shí)現(xiàn)一個(gè)簡(jiǎn)單的優(yōu)先級(jí)隊(duì)列
# example.py## Example of a priority queueimport heapqclass 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 useclass 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 win32Type "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')>>> 可以看出：第一次執(zhí)行pop()操作時(shí)返回的元素具有最高的優(yōu)先級(jí)；對(duì)于相同優(yōu)先級(jí)的兩個(gè)元素（foo和gork）返回的順序同它們插入到隊(duì)列時(shí)的順序相同。
在這段代碼中，隊(duì)列以元組(-priority, self._index, item)的形式組成，priority取負(fù)值是為了隊(duì)列按照從高到低的順序排列，這和堆默認(rèn)的從小到大的排序相反。
變量index的作用是對(duì)相同優(yōu)先級(jí)的元素以適當(dāng)?shù)捻樞蚺帕校貏e對(duì)同優(yōu)先級(jí)的元素間做比較操作時(shí)扮演了重要的角色。
Item實(shí)例無(wú)法進(jìn)行次序比較：
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)的形式來(lái)表示元素，只要優(yōu)先級(jí)不同，就可進(jìn)行比較：
a=(1,Item('foo'))b=(5,Item('bar'))c=(1,Item('gork'))print('a<b: ',a<b)print('a<c: ',a<c)>>> a<b: TrueTraceback (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)的方式建立元組，就可以避免相同優(yōu)先級(jí)無(wú)法比較的問(wèn)題，因?yàn)闆](méi)有哪兩個(gè)元組會(huì)有相同的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: Truea<c: True>>>如果想將這個(gè)隊(duì)列用于線程間通信，還需要增加適當(dāng)?shù)逆i和信號(hào)機(jī)制。
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
新聞熱點(diǎn)
疑難解答
圖片精選
