Python實(shí)現(xiàn)優(yōu)先級隊(duì)列結(jié)構(gòu)的方法詳解
最簡單的實(shí)現(xiàn)
一個(gè)隊(duì)列至少滿足2個(gè)方法,put和get.
借助最小堆來實(shí)現(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 模塊實(shí)現(xiàn)了一個(gè)簡單的優(yōu)先級隊(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)先級最高的元素。 另外注意到如果兩個(gè)有著相同優(yōu)先級的元素( foo 和 grok ),pop操作按照它們被插入到隊(duì)列的順序返回的。
函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 _queue 上插入和刪除第一個(gè)元素, 并且隊(duì)列_queue保證第一個(gè)元素?fù)碛凶钚?yōu)先級(1.4節(jié)已經(jīng)討論過這個(gè)問題)。 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)先級為負(fù)數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。 這個(gè)跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。
index 變量的作用是保證同等優(yōu)先級元素的正確排序。 通過保存一個(gè)不斷增加的 index 下標(biāo)變量,可以確保元素按照它們插入的順序排序。 而且, index 變量也在相同優(yōu)先級元素比較的時(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)先級不同就能比較。 但是如果兩個(gè)元素優(yōu)先級一樣的話,那么比較操作就會跟之前一樣出錯(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() >>>
通過引入另外的 index 變量組成三元組 (priority, index, item) ,就能很好的避免上面的錯(cuò)誤, 因?yàn)椴豢赡苡袃蓚€(gè)元素有相同的 index 值。Python在做元組比較時(shí)候,如果前面的比較以及可以確定結(jié)果了, 后面的比較操作就不會發(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和信號量機(jī)制。 可以查看12.3小節(jié)的例子演示是怎樣做的。
深入思考
函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 _queue 上插入和刪除第一個(gè)元素, 并且隊(duì)列_queue保證第一個(gè)元素?fù)碛凶钚?yōu)先級(1.4節(jié)已經(jīng)討論過這個(gè)問題)。 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)先級為負(fù)數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。 這個(gè)跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。
index 變量的作用是保證同等優(yōu)先級元素的正確排序。 通過保存一個(gè)不斷增加的 index 下標(biāo)變量,可以確保元素按照它們插入的順序排序。 而且, index 變量也在相同優(yōu)先級元素比較的時(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)先級不同就能比較。 但是如果兩個(gè)元素優(yōu)先級一樣的話,那么比較操作就會跟之前一樣出錯(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() >>>
通過引入另外的 index 變量組成三元組 (priority, index, item) ,就能很好的避免上面的錯(cuò)誤, 因?yàn)椴豢赡苡袃蓚€(gè)元素有相同的 index 值。Python在做元組比較時(shí)候,如果前面的比較以及可以確定結(jié)果了, 后面的比較操作就不會發(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和信號量機(jī)制。 可以查看12.3小節(jié)的例子演示是怎樣做的。
heapq 模塊的官方文檔有更詳細(xì)的例子程序以及對于堆理論及其實(shí)現(xiàn)的詳細(xì)說明。
相關(guān)文章
對Python中的條件判斷、循環(huán)以及循環(huán)的終止方法詳解
今天小編就為大家分享一篇對Python中的條件判斷、循環(huán)以及循環(huán)的終止方法詳解,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-02-02Python幫你解決手機(jī)qq微信內(nèi)存占用太多問題
你有沒有發(fā)現(xiàn)以前16G內(nèi)存也可以裝幾個(gè)游戲玩,現(xiàn)在128G的卻日常使用都不夠了?更不用說裝什么游戲,這其實(shí)是軟件內(nèi)存占用過多導(dǎo)致的,今天我們用python來清理下2022-02-02python 通過類中一個(gè)方法獲取另一個(gè)方法變量的實(shí)例
今天小編就為大家分享一篇python 通過類中一個(gè)方法獲取另一個(gè)方法變量的實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01