Python實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)的方法詳解

最簡(jiǎn)單的實(shí)現(xiàn)
一個(gè)隊(duì)列至少滿足2個(gè)方法,put和get.
借助最小堆來(lái)實(shí)現(xiàn).
這里按"值越大優(yōu)先級(jí)越高"的順序.    
#coding=utf-8
from heapq import heappush, heappop
class PriorityQueue:
  def __init__(self):
    self._queue = []
 
  def put(self, item, priority):
    heappush(self._queue, (-priority, item))
 
  def get(self):
    return heappop(self._queue)[-1]
 
q = PriorityQueue()
q.put('world', 1)
q.put('hello', 2)
print q.get()
print q.get()

使用heapq模塊來(lái)實(shí)現(xiàn)
下面的類(lèi)利用 heapq 模塊實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的優(yōu)先級(jí)隊(duì)列：    
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]
下面是它的使用方式：
  
>>> 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)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>
仔細(xì)觀察可以發(fā)現(xiàn)，第一個(gè) pop() 操作返回優(yōu)先級(jí)最高的元素。 另外注意到如果兩個(gè)有著相同優(yōu)先級(jí)的元素( foo 和 grok )，pop操作按照它們被插入到隊(duì)列的順序返回的。
 函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 _queue 上插入和刪除第一個(gè)元素， 并且隊(duì)列_queue保證第一個(gè)元素?fù)碛凶钚?yōu)先級(jí)(1.4節(jié)已經(jīng)討論過(guò)這個(gè)問(wèn)題)。 heappop() 函數(shù)總是返回”最小的”的元素，這就是保證隊(duì)列pop操作返回正確元素的關(guān)鍵。 另外，由于push和pop操作時(shí)間復(fù)雜度為O(log N)，其中N是堆的大小，因此就算是N很大的時(shí)候它們運(yùn)行速度也依舊很快。
在上面代碼中，隊(duì)列包含了一個(gè) (-priority, index, item) 的元組。 優(yōu)先級(jí)為負(fù)數(shù)的目的是使得元素按照優(yōu)先級(jí)從高到低排序。 這個(gè)跟普通的按優(yōu)先級(jí)從低到高排序的堆排序恰巧相反。
index 變量的作用是保證同等優(yōu)先級(jí)元素的正確排序。 通過(guò)保存一個(gè)不斷增加的 index 下標(biāo)變量，可以確保元素按照它們插入的順序排序。 而且， index 變量也在相同優(yōu)先級(jí)元素比較的時(shí)候起到重要作用。

為了闡明這些，先假定Item實(shí)例是不支持排序的：    
>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>
如果你使用元組 (priority, item) ，只要兩個(gè)元素的優(yōu)先級(jí)不同就能比較。 但是如果兩個(gè)元素優(yōu)先級(jí)一樣的話，那么比較操作就會(huì)跟之前一樣出錯(cuò)：    
>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>
通過(guò)引入另外的 index 變量組成三元組 (priority, index, item) ，就能很好的避免上面的錯(cuò)誤， 因?yàn)椴豢赡苡袃蓚€(gè)元素有相同的 index 值。Python在做元組比較時(shí)候，如果前面的比較以及可以確定結(jié)果了， 后面的比較操作就不會(huì)發(fā)生了：    
>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>
如果你想在多個(gè)線程中使用同一個(gè)隊(duì)列，那么你需要增加適當(dāng)?shù)逆i和信號(hào)量機(jī)制。 可以查看12.3小節(jié)的例子演示是怎樣做的。
深入思考
函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 _queue 上插入和刪除第一個(gè)元素， 并且隊(duì)列_queue保證第一個(gè)元素?fù)碛凶钚?yōu)先級(jí)(1.4節(jié)已經(jīng)討論過(guò)這個(gè)問(wèn)題)。 heappop() 函數(shù)總是返回”最小的”的元素，這就是保證隊(duì)列pop操作返回正確元素的關(guān)鍵。 另外，由于push和pop操作時(shí)間復(fù)雜度為O(log N)，其中N是堆的大小，因此就算是N很大的時(shí)候它們運(yùn)行速度也依舊很快。
在上面代碼中，隊(duì)列包含了一個(gè) (-priority, index, item) 的元組。 優(yōu)先級(jí)為負(fù)數(shù)的目的是使得元素按照優(yōu)先級(jí)從高到低排序。 這個(gè)跟普通的按優(yōu)先級(jí)從低到高排序的堆排序恰巧相反。
index 變量的作用是保證同等優(yōu)先級(jí)元素的正確排序。 通過(guò)保存一個(gè)不斷增加的 index 下標(biāo)變量，可以確保元素按照它們插入的順序排序。 而且， index 變量也在相同優(yōu)先級(jí)元素比較的時(shí)候起到重要作用。
為了闡明這些，先假定Item實(shí)例是不支持排序的：    
>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

如果你使用元組 (priority, item) ，只要兩個(gè)元素的優(yōu)先級(jí)不同就能比較。 但是如果兩個(gè)元素優(yōu)先級(jí)一樣的話，那么比較操作就會(huì)跟之前一樣出錯(cuò)：    
>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>
通過(guò)引入另外的 index 變量組成三元組 (priority, index, item) ，就能很好的避免上面的錯(cuò)誤， 因?yàn)椴豢赡苡袃蓚€(gè)元素有相同的 index 值。Python在做元組比較時(shí)候，如果前面的比較以及可以確定結(jié)果了， 后面的比較操作就不會(huì)發(fā)生了：    
>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>
如果你想在多個(gè)線程中使用同一個(gè)隊(duì)列，那么你需要增加適當(dāng)?shù)逆i和信號(hào)量機(jī)制。 可以查看12.3小節(jié)的例子演示是怎樣做的。
heapq 模塊的官方文檔有更詳細(xì)的例子程序以及對(duì)于堆理論及其實(shí)現(xiàn)的詳細(xì)說(shuō)明。