當前位置:成語大全網 - 新華字典 - Python headq模塊淺析

Python headq模塊淺析

參考:

heapq Documentation

淺析Python heapq模塊 堆數據結構

在Python中也對堆這種數據結構進行了模塊化,我們可以通過調用heapq模塊來建立堆這種數據結構,同時heapq模塊也提供了相應的方法來對堆做操作。

heap = [] #創建了壹個空堆

item = heap[0] #查看堆中最小值,不彈出

heappush(heap,item) #往堆中插入壹條新的值

item = heappop(heap) #從堆中彈出最小值, 如果堆為空報 IndexError 異常

heappushpop() #1.將值插入到堆中 2.彈出堆中的最小值。

P.S. 1. 可以保證彈出最小元素 2. 效率比先heappush再heappop快

heapify(x) #以線性時間講壹個列表轉化為堆

item = heapreplace(heap,item) #彈出並返回最小值,然後將heapqreplace方法中item的值插入到堆中,堆的整體結構不會發生改變。如果堆為空報 IndexError 異常。 在需要保證堆大小不變的適合使用

P.S. 1. 彈出的元素可能比加入的item大 2. 效率比先heappop再heappush快

merge(*iterables, key=None, reverse=False) #合並多個堆然後輸出

nlargest(n , iterbale, key=None) #從堆中找出做大的N個數,key的作用和sorted( )方法裏面的key類似,用列表元素的某個屬性和函數作為關鍵字

nsmallest(n, iterable, key=None) #找到堆中最小的N個數用法同上

該段為heapq Documentation裏節選的翻譯

堆作為數據結構在內存和二級緩存中充當了重要的角色。優先隊列中也會經常使用堆,這也就給堆數據結構提出了很多挑戰。例如內存中存放了數多個計劃任務的時候我們可以定義壹個數列list(priority,task)來保存在堆結構中。但是這樣就出現了很多問題 :

1.排序的穩定性:當任務加入到堆中時,如果兩個任務有同等的優先級,兩個任務實際上在列表裏是沒什麽區別的,那我怎麽得到返回值?

2.在Python3以後的版本中,如果元組(priority,task)priority是壹樣的,而且task沒有壹個默認的比較參照值,那這樣我們其實是沒有辦法來比較的。

3.如果壹個任務的優先級發生了改變,那麽我們如何來處理該任務在相應堆中優先級的變化,堆中位置肯定會改變。

4.如果壹個任務因為要等待其他的任務(最簡單的比方,等待父進程)而照成懸掛狀態,我們如何在堆中去找到它並且做相應的操作(降低優先級或者刪除該任務)

解決前兩個問題的方法我們可以采用三元數組的方法。設置壹個優先級,壹個條目值,壹個任務值。即使當兩個任務有相同優先級的時候,因為條目值不壹樣可以幫助cpu來裁決它們被加載的順序。

剩下需要解決的問題是如何找到被懸掛而推遲的任務,然後嘗試去修改優先級或者永久刪除這個任務。我們可以使用字典,來指向堆中某個任務的條目值。

最後就是刪除操作,刪除會改變堆的結構。為了保證堆結構的特性,我們可以標記已有將被刪除的任務的條目值,然後將該任務重新打標加入到堆中。