python 優(yōu)先級(jí)隊(duì)列PriorityQueue

本文內(nèi)容來(lái)自于 python隊(duì)列queue 之優(yōu)先級(jí)隊(duì)列

成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)頁(yè)設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、響應(yīng)式網(wǎng)站設(shè)計(jì)、程序開(kāi)發(fā)、網(wǎng)站優(yōu)化、微網(wǎng)站、微信小程序等，憑借多年來(lái)在互聯(lián)網(wǎng)的打拼，我們?cè)诨ヂ?lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了豐富的網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷經(jīng)驗(yàn)，集策劃、開(kāi)發(fā)、設(shè)計(jì)、營(yíng)銷、管理等多方位專業(yè)化運(yùn)作于一體。

PriorityQueue創(chuàng)建的是大頂堆，即值越小優(yōu)先級(jí)越高。

打印結(jié)果

Python數(shù)據(jù)結(jié)構(gòu)-隊(duì)列與廣度優(yōu)先搜索（Queue）

隊(duì)列（Queue） ：簡(jiǎn)稱為隊(duì)，一種線性表數(shù)據(jù)結(jié)構(gòu)，是一種只允許在表的一端進(jìn)行插入操作，而在表的另一端進(jìn)行刪除操作的線性表。

我們把隊(duì)列中允許插入的一端稱為 「隊(duì)尾（rear）」 ；把允許刪除的另一端稱為 「隊(duì)頭（front）」 。當(dāng)表中沒(méi)有任何數(shù)據(jù)元素時(shí)，稱之為 「空隊(duì)」 。

廣度優(yōu)先搜索算法（Breadth First Search） ：簡(jiǎn)稱為 BFS，又譯作寬度優(yōu)先搜索 / 橫向優(yōu)先搜索。是一種用于遍歷或搜索樹(shù)或圖的算法。該算法從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷樹(shù)或圖的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問(wèn)，則算法中止。

廣度優(yōu)先遍歷 類似于樹(shù)的層次遍歷過(guò)程 。呈現(xiàn)出一層一層向外擴(kuò)張的特點(diǎn)。先看到的節(jié)點(diǎn)先訪問(wèn)，后看到的節(jié)點(diǎn)后訪問(wèn)。遍歷到的節(jié)點(diǎn)順序符合「先進(jìn)先出」的特點(diǎn)，所以廣度優(yōu)先搜索可以通過(guò)「隊(duì)列」來(lái)實(shí)現(xiàn)。

力扣933

游戲時(shí)，隊(duì)首始終是持有土豆的人

模擬游戲開(kāi)始，隊(duì)首的人出隊(duì)，之后再到隊(duì)尾（類似于循環(huán)隊(duì)列）

傳遞了num次之后，將隊(duì)首的人移除

如此反復(fù)，直到隊(duì)列中剩余一人

多人共用一臺(tái)打印機(jī)，采取“先到先服務(wù)”的隊(duì)列策略來(lái)執(zhí)行打印任務(wù)

需要解決的問(wèn)題：1 打印系統(tǒng)的容量是多少？2 在能夠接受的等待時(shí)間內(nèi)，系統(tǒng)可容納多少用戶以多高的頻率提交打印任務(wù)？

輸入：abba

輸出：False

思路：1 先將需要判定的詞從隊(duì)尾加入 deque; 2從兩端同時(shí)移除字符并判斷是否相同，直到deque中剩余0個(gè)（偶數(shù)）或1個(gè)字符（奇數(shù)）

內(nèi)容參考：

Python Queue 入門

Queue 叫隊(duì)列，是數(shù)據(jù)結(jié)構(gòu)中的一種，基本上所有成熟的編程語(yǔ)言都內(nèi)置了對(duì) Queue 的支持。

Python 中的 Queue 模塊實(shí)現(xiàn)了多生產(chǎn)者和多消費(fèi)者模型，當(dāng)需要在多線程編程中非常實(shí)用。而且該模塊中的 Queue 類實(shí)現(xiàn)了鎖原語(yǔ)，不需要再考慮多線程安全問(wèn)題。

該模塊內(nèi)置了三種類型的 Queue，分別是 class queue.Queue(maxsize=0) ， class queue.LifoQueue(maxsize=0) 和 class queue.PriorityQueue(maxsize=0) 。它們?nèi)齻€(gè)的區(qū)別僅僅是取出時(shí)的順序不一致而已。

Queue 是一個(gè) FIFO 隊(duì)列，任務(wù)按照添加的順序被取出。

LifoQueue 是一個(gè) LIFO 隊(duì)列，類似堆棧，后添加的任務(wù)先被取出。

PriorityQueue 是一個(gè)優(yōu)先級(jí)隊(duì)列，隊(duì)列里面的任務(wù)按照優(yōu)先級(jí)排序，優(yōu)先級(jí)高的先被取出。

如你所見(jiàn)，就是上面所說(shuō)的三種不同類型的內(nèi)置隊(duì)列，其中 maxsize 是個(gè)整數(shù)，用于設(shè)置可以放入隊(duì)列中的任務(wù)數(shù)的上限。當(dāng)達(dá)到這個(gè)大小的時(shí)候，插入操作將阻塞至隊(duì)列中的任務(wù)被消費(fèi)掉。如果 maxsize 小于等于零，則隊(duì)列尺寸為無(wú)限大。

向隊(duì)列中添加任務(wù)，直接調(diào)用 put() 函數(shù)即可

put() 函數(shù)完整的函數(shù)簽名如下 Queue.put(item, block=True, timeout=None) ，如你所見(jiàn)，該函數(shù)有兩個(gè)可選參數(shù)。

默認(rèn)情況下，在隊(duì)列滿時(shí)，該函數(shù)會(huì)一直阻塞，直到隊(duì)列中有空余的位置可以添加任務(wù)為止。如果 timeout 是正數(shù)，則最多阻塞 timeout 秒，如果這段時(shí)間內(nèi)還沒(méi)有空余的位置出來(lái)，則會(huì)引發(fā) Full 異常。

當(dāng) block 為 false 時(shí)，timeout 參數(shù)將失效。同時(shí)如果隊(duì)列中沒(méi)有空余的位置可添加任務(wù)則會(huì)引發(fā) Full 異常，否則會(huì)直接把任務(wù)放入隊(duì)列并返回，不會(huì)阻塞。

另外，還可以通過(guò) Queue.put_nowait(item) 來(lái)添加任務(wù)，相當(dāng)于 Queue.put(item, False) ，不再贅述。同樣，在隊(duì)列滿時(shí)，該操作會(huì)引發(fā) Full 異常。

從隊(duì)列中獲取任務(wù)，直接調(diào)用 get() 函數(shù)即可。

與 put() 函數(shù)一樣， get() 函數(shù)也有兩個(gè)可選參數(shù)，完整簽名如下 Queue.get(block=True, timeout=None) 。

默認(rèn)情況下，當(dāng)隊(duì)列空時(shí)調(diào)用該函數(shù)會(huì)一直阻塞，直到隊(duì)列中有任務(wù)可獲取為止。如果 timeout 是正數(shù)，則最多阻塞 timeout 秒，如果這段時(shí)間內(nèi)還沒(méi)有任務(wù)可獲取，則會(huì)引發(fā) Empty 異常。

當(dāng) block 為 false 時(shí)，timeout 參數(shù)將失效。同時(shí)如果隊(duì)列中沒(méi)有任務(wù)可獲取則會(huì)立刻引發(fā) Empty 異常，否則會(huì)直接獲取一個(gè)任務(wù)并返回，不會(huì)阻塞。

另外，還可以通過(guò) Queue.get_nowait() 來(lái)獲取任務(wù)，相當(dāng)于 Queue.get(False) ，不再贅述。同樣，在隊(duì)列為空時(shí)，該操作會(huì)引發(fā) Empty 異常。

Queue.qsize() 函數(shù)返回隊(duì)列的大小。注意這個(gè)大小不是精確的，qsize() 0 不保證后續(xù)的 get() 不被阻塞，同樣 qsize() maxsize 也不保證 put() 不被阻塞。

如果隊(duì)列為空，返回 True ，否則返回 False 。如果 empty() 返回 True ，不保證后續(xù)調(diào)用的 put() 不被阻塞。類似的，如果 empty() 返回 False ，也不保證后續(xù)調(diào)用的 get() 不被阻塞。

如果隊(duì)列是滿的返回 True ，否則返回 False 。如果 full() 返回 True 不保證后續(xù)調(diào)用的 get() 不被阻塞。類似的，如果 full() 返回 False 也不保證后續(xù)調(diào)用的 put() 不被阻塞。

queue.Queue() 是 FIFO 隊(duì)列，出隊(duì)順序跟入隊(duì)順序是一致的。

queue.LifoQueue() 是 LIFO 隊(duì)列，出隊(duì)順序跟入隊(duì)順序是完全相反的，類似于棧。

優(yōu)先級(jí)隊(duì)列中的任務(wù)順序跟放入時(shí)的順序是無(wú)關(guān)的，而是按照任務(wù)的大小來(lái)排序，最小值先被取出。那任務(wù)比較大小的規(guī)則是怎么樣的呢。

注意，因?yàn)榱斜淼谋容^對(duì)規(guī)則是按照下標(biāo)順序來(lái)比較的，所以在沒(méi)有比較出大小之前 ，隊(duì)列中所有列表對(duì)應(yīng)下標(biāo)位置的元素類型要一致。

好比 [2,1] 和 ["1","b"] 因?yàn)榈谝粋€(gè)位置的元素類型不一樣，所以是沒(méi)有辦法比較大小的，所以也就放入不了優(yōu)先級(jí)隊(duì)列。

然而對(duì)于 [2,1] 和 [1,"b"] 來(lái)說(shuō)即使第二個(gè)元素的類型不一致也是可以放入優(yōu)先級(jí)隊(duì)列的，因?yàn)橹恍枰容^第一個(gè)位置元素的大小就可以比較出結(jié)果了，就不需要比較第二個(gè)位置元素的大小了。

但是對(duì)于 [2,1] 和 1 [2,"b"] 來(lái)說(shuō)，則同樣不可以放入優(yōu)先級(jí)隊(duì)列，因?yàn)樾枰容^第二個(gè)位置的元素才可以比較出結(jié)果，然而第二個(gè)位置的元素類型是不一致的，無(wú)法比較大小。

綜上，也就是說(shuō)， 直到在比較出結(jié)果之前，對(duì)應(yīng)下標(biāo)位置的元素類型都是需要一致的 。

下面我們自定義一個(gè)動(dòng)物類型，希望按照年齡大小來(lái)做優(yōu)先級(jí)排序。年齡越小優(yōu)先級(jí)越高。

本章節(jié)介紹了隊(duì)列以及其常用操作。因?yàn)殛?duì)列默認(rèn)實(shí)現(xiàn)了鎖原語(yǔ)，因此在多線程編程中就不需要再考慮多線程安全問(wèn)題了，對(duì)于程序員來(lái)說(shuō)相當(dāng)友好了。

sorted函數(shù)python

sorted函數(shù)python介紹如下

sorted() 作為?Python?內(nèi)置函數(shù)之一，其功能是對(duì)序列（列表、元組、字典、集合、還包括字符串）進(jìn)行排序。

sorted() 函數(shù)的基本語(yǔ)法格式如下

list = sorted(iterable, key=None, reverse=False)

其中，iterable 表示指定的序列，key 參數(shù)可以自定義排序規(guī)則；reverse 參數(shù)指定以升序（False，默認(rèn)）還是降序（True）進(jìn)行排序。sorted() 函數(shù)會(huì)返回一個(gè)排好序的列表。

注意，key 參數(shù)和 reverse 參數(shù)是可選參數(shù)，即可以使用，也可以忽略。

演示sorted()函數(shù)的基本代碼用法：

#對(duì)列表進(jìn)行排序

a = [5,3,4,2,1]

print(sorted(a))

#對(duì)元組進(jìn)行排序

a = (5,4,3,1,2)

print(sorted(a))

#字典默認(rèn)按照key進(jìn)行排序

a = {4:1,\

5:2,\

3:3,\

2:6,\

1:8}

print(sorted(a.items()))

#對(duì)集合進(jìn)行排序

a = {1,5,3,2,4}

print(sorted(a))

#對(duì)字符串進(jìn)行排序

a = "51423"

print(sorted(a))