摘要:項(xiàng)目地址中內(nèi)置的庫和分別提供了堆和優(yōu)先隊(duì)列結(jié)構(gòu),其中優(yōu)先隊(duì)列本身也是基于實(shí)現(xiàn)的,因此我們這次重點(diǎn)看一下。堆可以用于實(shí)現(xiàn)調(diào)度器例見之協(xié)程,更常用的是優(yōu)先隊(duì)列例如。
項(xiàng)目地址:https://git.io/pytips
Python 中內(nèi)置的 heapq 庫和 queue 分別提供了堆和優(yōu)先隊(duì)列結(jié)構(gòu),其中優(yōu)先隊(duì)列 queue.PriorityQueue 本身也是基于 heapq 實(shí)現(xiàn)的,因此我們這次重點(diǎn)看一下 heapq。
堆(Heap)是一種特殊形式的完全二叉樹,其中父節(jié)點(diǎn)的值總是大于子節(jié)點(diǎn),根據(jù)其性質(zhì),Python 中可以用一個(gè)滿足 heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] 的列表來實(shí)現(xiàn)(heapq 也確實(shí)是這么做的)。堆可以用于實(shí)現(xiàn)調(diào)度器(例見:Python 3.5 之協(xié)程),更常用的是優(yōu)先隊(duì)列(例如:ImageColorTheme)。
heapq 提供了下面這些方法:
import heapq print(heapq.__all__)
["heappush", "heappop", "heapify", "heapreplace", "merge", "nlargest", "nsmallest", "heappushpop"]
由于 Heap 是通過列表實(shí)現(xiàn)的,我們可以直接用列表創(chuàng)建:
from heapq import * heap = [] heappush(heap, 3) heappush(heap, 2) heappush(heap, 1) print(heap)
[1, 3, 2]pop 或 sort 前要確保 heapify
或者通過 heapify 將普通列表轉(zhuǎn)化為 Heap:
heap = list(reversed(range(5))) print("List: ", heap) heapify(heap) print("Heap: ", heap)
List: [4, 3, 2, 1, 0] Heap: [0, 1, 2, 4, 3]
每次從 Heap 中 pop 出來的元素都是最小的(因而可以據(jù)此實(shí)現(xiàn)堆排序):
heap = [5,4,3,2,1] heapify(heap) print(heappop(heap)) print(heappop(heap)) print(heappop(heap))
1 2 3優(yōu)先隊(duì)列
queue.PriorityQueue 實(shí)際上只是對 heapq 的簡單封裝,直接使用其 heappush/heappop 方法:
from queue import PriorityQueue as PQueue pq = PQueue() pq.put((5 * -1, "Python")) pq.put((4 * -1, "C")) pq.put((3 * -1, "Js")) print("Inside PriorityQueue: ", pq.queue) # 內(nèi)部存儲(chǔ) while not pq.empty(): print(pq.get()[1])
Inside PriorityQueue: [(-5, "Python"), (-4, "C"), (-3, "Js")] Python C Js
由于 heapq 是最小堆,而通常 PriorityQueue 用在較大有限制的排前面,所以需要給 priority * -1。
sorted 一定是 Heap,反之未必需要注意的是,雖然 Heap 通過 List 實(shí)習(xí),但未經(jīng)過 heapify() 處理的仍然是一個(gè)普通的 List,而 heappush 和 heappop 操作每次都會(huì)對 Heap 進(jìn)行重新整理。此外,一個(gè) Heap 列表不一定是正確排序的,但是經(jīng)過 list.sort() 的列表一定是 Heap:
import random lst = [random.randrange(1, 100) for _ in range(5)] lst.sort() print("List: ", lst) print("Poped: ", heappop(lst)) heappush(lst, 4) print("Heap: ", lst)
List: [24, 55, 81, 83, 87] Poped: 24 Heap: [4, 55, 81, 87, 83]最大/最小的 N 個(gè)數(shù)
Heap 還提供了 nsmallest 和 nlargest 方法用于取出前 n 個(gè)最大/最小數(shù):
heap = [random.randrange(1, 1000) for _ in range(1000)] heapify(heap) print("N largest: ", nlargest(10, heap)) print("N smallest: ", nsmallest(10, heap)) print(len(heap)) # 不原地修改
N largest: [999, 999, 998, 994, 992, 991, 990, 988, 985, 982] N smallest: [1, 1, 1, 2, 4, 5, 5, 6, 6, 9] 1000合并(排序)
merge 方法用于將兩個(gè) Heap 進(jìn)行合并:
heapA = sorted([random.randrange(1, 100) for _ in range(3)]) heapB = sorted([random.randrange(1, 100) for _ in range(3)]) merged = [] for i in merge(heapA, heapB): merged.append(i) print(merged)
[5, 29, 66, 66, 70, 99]
最后兩個(gè)方法 heapreplace 和 heappushpop 分別相當(dāng)于:
lstA = [1,2,3,4,5] lstB = [1,2,3,4,5] poped = heapreplace(lstA, 0) print("lstA: ", lstA, "poped: ", poped) # is equal to... poped = heappop(lstB) heappush(lstB, 0) print("lstB: ", lstA, "poped: ", poped) print("*"*30) poped = heappushpop(lstA, 9) print("lstA: ", lstA, "poped: ", poped) # is equal to... heappush(lstB, 9) poped = heappop(lstB) print("lstB: ", lstB, "poped: ", poped)
lstA: [0, 2, 3, 4, 5] poped: 1 lstB: [0, 2, 3, 4, 5] poped: 1 ****************************** lstA: [2, 4, 3, 9, 5] poped: 0 lstB: [2, 4, 3, 5, 9] poped: 0
這兩個(gè)方法的執(zhí)行效率要比分開寫的方法高,但要注意 heapreplace 要取代的值是否比 heap[0] 大,如果不是,可以用更有效的方法:
item = 0 lstA = [1,2,3,4,5] if item < lstA[0]: # replace poped = lstA[0] lstA[0] = item print("lstA: ", lstA, "poped: ", poped)
lstA: [0, 2, 3, 4, 5] poped: 1
歡迎關(guān)注公眾號(hào) PyHub!
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/37859.html
摘要:一個(gè)常見的例子就是優(yōu)先隊(duì)列,還有排序算法之一的堆排序。另外我們還將學(xué)習(xí)堆排序,并將使用實(shí)現(xiàn)堆。堆排序在堆排序中,我們需要用給定的值構(gòu)建一個(gè)一個(gè)堆。偽代碼如下從上面的偽代碼可以看到,堆排序的第一步就是構(gòu)建一個(gè)堆。 堆是什么? 堆是基于樹抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu),用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個(gè)常見的例子就是優(yōu)先隊(duì)列,還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...
摘要:堆與棧棧由編譯器自動(dòng)分配存放函數(shù)的參數(shù)值局部變量的值等其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧堆一般由程序員分配釋放若程序員不釋放程序結(jié)束時(shí)可能由回收這里是指操作系統(tǒng)區(qū)別和聯(lián)系申請方式堆由程序員自己申請并指明大小在語言中的函數(shù)棧由系統(tǒng)自動(dòng)分配聲明在函 堆與棧 棧(stack): 由編譯器自動(dòng)分配, 存放函數(shù)的參數(shù)值, 局部變量的值等. 其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧. 堆(heap): 一般由...
摘要:項(xiàng)目地址我之前翻譯了協(xié)程原理這篇文章之后嘗試用了模式下的協(xié)程進(jìn)行異步開發(fā),確實(shí)感受到協(xié)程所帶來的好處至少是語法上的。 項(xiàng)目地址:https://git.io/pytips 我之前翻譯了Python 3.5 協(xié)程原理這篇文章之后嘗試用了 Tornado + Motor 模式下的協(xié)程進(jìn)行異步開發(fā),確實(shí)感受到協(xié)程所帶來的好處(至少是語法上的:D)。至于協(xié)程的 async/await 語法是如...
摘要:這里的關(guān)鍵詞函數(shù)必須明確指明,不能通過位置推斷則代表任意數(shù)量的關(guān)鍵詞參數(shù)添加的新特性,使得可以在函數(shù)參數(shù)之外使用這里的逗號(hào)不能漏掉所謂的解包實(shí)際上可以看做是去掉的元組或者是去掉的字典。 項(xiàng)目地址:https://git.io/pytips 函數(shù)調(diào)用的參數(shù)規(guī)則與解包 Python 的函數(shù)在聲明參數(shù)時(shí)大概有下面 4 種形式: 不帶默認(rèn)值的:def func(a): pass 帶有默認(rèn)值的...
摘要:中關(guān)于線程的標(biāo)準(zhǔn)庫是,之前在版本中的在之后更名為,無論是還是都應(yīng)該盡量避免使用較為底層的而應(yīng)該使用。而與線程相比,協(xié)程尤其是結(jié)合事件循環(huán)無論在編程模型還是語法上,看起來都是非常友好的單線程同步過程。 項(xiàng)目地址:https://git.io/pytips 要說到線程(Thread)與協(xié)程(Coroutine)似乎總是需要從并行(Parallelism)與并發(fā)(Concurrency)談起...
閱讀 1660·2021-11-23 10:07
閱讀 2653·2019-08-30 11:10
閱讀 2834·2019-08-29 17:08
閱讀 1778·2019-08-29 15:42
閱讀 3163·2019-08-29 12:57
閱讀 2396·2019-08-28 18:06
閱讀 3544·2019-08-27 10:56
閱讀 383·2019-08-26 11:33