最簡單的實現(xiàn)
一個隊列至少滿足2個方法,put和get.
借助最小堆來實現(xiàn).
這里按"值越大優(yōu)先級越高"的順序.

#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模塊來實現(xiàn)
下面的類利用 heapq 模塊實現(xiàn)了一個簡單的優(yōu)先級隊列：

import 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]

下面是它的使用方式：

>>> 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')>>>

仔細觀察可以發(fā)現(xiàn)，第一個 pop() 操作返回優(yōu)先級最高的元素。 另外注意到如果兩個有著相同優(yōu)先級的元素( foo 和 grok )，pop操作按照它們被插入到隊列的順序返回的。

 函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊列 _queue 上插入和刪除第一個元素， 并且隊列_queue保證第一個元素擁有最小優(yōu)先級(1.4節(jié)已經(jīng)討論過這個問題)。 heappop() 函數(shù)總是返回”最小的”的元素，這就是保證隊列pop操作返回正確元素的關鍵。 另外，由于push和pop操作時間復雜度為O(log N)，其中N是堆的大小，因此就算是N很大的時候它們運行速度也依舊很快。

在上面代碼中，隊列包含了一個 (-priority, index, item) 的元組。 優(yōu)先級為負數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。 這個跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。

index 變量的作用是保證同等優(yōu)先級元素的正確排序。 通過保存一個不斷增加的 index 下標變量，可以確保元素按照它們插入的順序排序。 而且， index 變量也在相同優(yōu)先級元素比較的時候起到重要作用。

為了闡明這些，先假定Item實例是不支持排序的：

>>> a = Item('foo')>>> b = Item('bar')>>> a < bTraceback (most recent call last):File "<stdin>", line 1, in <module>TypeError: unorderable types: Item() < Item()>>>

如果你使用元組 (priority, item) ，只要兩個元素的優(yōu)先級不同就能比較。 但是如果兩個元素優(yōu)先級一樣的話，那么比較操作就會跟之前一樣出錯：

>>> a = (1, Item('foo'))>>> b = (5, Item('bar'))>>> a < bTrue>>> c = (1, Item('grok'))>>> a < cTraceback (most recent call last):File "<stdin>", line 1, in <module>TypeError: unorderable types: Item() < Item()>>>

通過引入另外的 index 變量組成三元組 (priority, index, item) ，就能很好的避免上面的錯誤， 因為不可能有兩個元素有相同的 index 值。Python在做元組比較時候，如果前面的比較以及可以確定結果了， 后面的比較操作就不會發(fā)生了：

>>> a = (1, 0, Item('foo'))>>> b = (5, 1, Item('bar'))>>> c = (1, 2, Item('grok'))>>> a < bTrue>>> a < cTrue>>>

如果你想在多個線程中使用同一個隊列，那么你需要增加適當?shù)逆i和信號量機制。 可以查看12.3小節(jié)的例子演示是怎樣做的。

深入思考
函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊列 _queue 上插入和刪除第一個元素， 并且隊列_queue保證第一個元素擁有最小優(yōu)先級(1.4節(jié)已經(jīng)討論過這個問題)。 heappop() 函數(shù)總是返回”最小的”的元素，這就是保證隊列pop操作返回正確元素的關鍵。 另外，由于push和pop操作時間復雜度為O(log N)，其中N是堆的大小，因此就算是N很大的時候它們運行速度也依舊很快。

在上面代碼中，隊列包含了一個 (-priority, index, item) 的元組。 優(yōu)先級為負數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。 這個跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。

index 變量的作用是保證同等優(yōu)先級元素的正確排序。 通過保存一個不斷增加的 index 下標變量，可以確保元素按照它們插入的順序排序。 而且， index 變量也在相同優(yōu)先級元素比較的時候起到重要作用。

為了闡明這些，先假定Item實例是不支持排序的：

>>> a = Item('foo')>>> b = Item('bar')>>> a < bTraceback (most recent call last):File "<stdin>", line 1, in <module>TypeError: unorderable types: Item() < Item()>>>

如果你使用元組 (priority, item) ，只要兩個元素的優(yōu)先級不同就能比較。 但是如果兩個元素優(yōu)先級一樣的話，那么比較操作就會跟之前一樣出錯：

>>> a = (1, Item('foo'))>>> b = (5, Item('bar'))>>> a < bTrue>>> c = (1, Item('grok'))>>> a < cTraceback (most recent call last):File "<stdin>", line 1, in <module>TypeError: unorderable types: Item() < Item()>>>

通過引入另外的 index 變量組成三元組 (priority, index, item) ，就能很好的避免上面的錯誤， 因為不可能有兩個元素有相同的 index 值。Python在做元組比較時候，如果前面的比較以及可以確定結果了， 后面的比較操作就不會發(fā)生了：

>>> a = (1, 0, Item('foo'))>>> b = (5, 1, Item('bar'))>>> c = (1, 2, Item('grok'))>>> a < bTrue>>> a < cTrue>>>

如果你想在多個線程中使用同一個隊列，那么你需要增加適當?shù)逆i和信號量機制。 可以查看12.3小節(jié)的例子演示是怎樣做的。

heapq 模塊的官方文檔有更詳細的例子程序以及對于堆理論及其實現(xiàn)的詳細說明。