av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術(shù)文章
文章詳情頁

Python實(shí)現(xiàn)一個優(yōu)先級隊(duì)列的方法

瀏覽:40日期:2022-07-15 16:20:32

問題

怎樣實(shí)現(xiàn)一個按優(yōu)先級排序的隊(duì)列? 并且在這個隊(duì)列上面每次 pop 操作總是返回優(yōu)先級最高的那個元素

解決方案

下面的類利用 heapq 模塊實(shí)現(xiàn)了一個簡單的優(yōu)先級隊(duì)列:

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

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

討論

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

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

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

為了闡明這些,先假定 Item 實(shí)例是不支持排序的:

>>> 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) ,就能很好的避免上面的錯誤, 因?yàn)椴豢赡苡袃蓚€元素有相同的 index 值。Python 在做元組比較時候,如果前面的比較已經(jīng)可以確定結(jié)果了, 后面的比較操作就不會發(fā)生了:

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

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

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

以上就是Python實(shí)現(xiàn)一個優(yōu)先級隊(duì)列的方法的詳細(xì)內(nèi)容,更多關(guān)于Python實(shí)現(xiàn)優(yōu)先級隊(duì)列的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章!

標(biāo)簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 日韩精品一区二区三区 | 欧美一级免费 | 少妇特黄a一区二区三区88av | 亚洲aⅴ一区二区 | 国产乱码精品一区二区三区忘忧草 | 国内精品久久久久久 | 欧美性乱 | 日本一区二区高清视频 | 亚洲精品一区av在线播放 | 日韩在线成人 | 精品国产乱码久久久久久影片 | 成年人在线电影 | av黄色免费 | 欧美日韩在线免费观看 | 一级毛片视频 | 天天干com| 在线播放国产一区二区三区 | 欧美久久一区二区 | 国产乱码精品一品二品 | 超碰日本 | 一区二区三区国产 | 日本黄色大片免费看 | 日韩在线观看视频一区 | 国产极品粉嫩美女呻吟在线看人 | 99久久精品免费看国产四区 | 午夜黄色影院 | 亚洲精品一区中文字幕乱码 | 国产精品久久久免费 | 国产精品一区二区视频 | 国产精品久久久久久吹潮 | 一区二区国产精品 | 久久久一区二区三区 | 久久久久久中文字幕 | 在线久草 | 欧美大片在线观看 | 在线视频国产一区 | 国产精品高清在线 | 久久激情视频 | 日韩精品国产精品 | 免费精品国产 | 谁有毛片 |