實現一個優先級隊列

問題

怎樣實現一個按優先級排序的隊列？并且在這個隊列上面每次pop操作總是返回優先級最高的那個元素。

解法

下面的類利用 heapq 模塊實現了一個簡單的優先級隊列：

import heapqclass PriorityQueue:def __init__(self):self._queue = []self._index = 0def push(self, item, priority):heapq.heappush(self._queue, (-priority, self._index, item))self._index += 1def 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') >>>

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

討論

函數heapq.heappush()和
heapq.heappop()分別在隊列queue上插入和刪除第一個元素，并且隊列queue保證第一個元素擁有最小優先級。heappop()函數總是返回“最小的”的元素，這就是保證隊列pop操作返回正確元素的關鍵。另外，由于push和pop操作時間復雜度為O(logN)，其中N是堆的大小，因此就算是N很大的時候它們運行速度也依舊很快。

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

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

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

>>> 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)，只要兩個元素的優先級不同就能比較。但是如果兩個元素優先級一樣的話，那么比較操作就會跟之前一樣出錯：

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

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

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

如果你想在多個線程中使用同一個隊列，那么你需要增加適當的鎖和信號量機制。

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

總結

以上是生活随笔為你收集整理的《Python Cookbook 3rd》笔记（1.5）：实现一个优先级队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。