Python中的heapq模塊源碼詳析
起步
這是一個相當(dāng)實用的內(nèi)置模塊，但是很多人竟然不知道他的存在——筆者也是今天偶然看到的，哎……盡管如此，還是改變不了這個模塊好用的事實
heapq 模塊實現(xiàn)了適用于Python列表的最小堆排序算法。
堆是一個樹狀的數(shù)據(jù)結(jié)構(gòu)，其中的子節(jié)點都與父母排序順序關(guān)系。因為堆排序中的樹是滿二叉樹，因此可以用列表來表示樹的結(jié)構(gòu)，使得元素 N 的子元素位于 2N + 1 和 2N + 2 的位置（對于從零開始的索引）。
本文內(nèi)容將分為三個部分，第一個部分簡單介紹 heapq 模塊的使用；第二部分回顧堆排序算法；第三部分分析heapq中的實現(xiàn)。
heapq 的使用
創(chuàng)建堆有兩個基本的方法：heappush() 和 heapify()，取出堆頂元素用 heappop()。
heappush() 是用來向已有的堆中添加元素，一般從空列表開始構(gòu)建：
import heapq
data = [97, 38, 27, 50, 76, 65, 49, 13]
heap = []
for n in data:
heapq.heappush(heap, n)
print('pop:', heapq.heappop(heap)) # pop: 13
print(heap) # [27, 50, 38, 97, 76, 65, 49]
如果數(shù)據(jù)已經(jīng)在列表中，則使用 heapify() 進行重排：
import heapq
data = [97, 38, 27, 50, 76, 65, 49, 13]
heapq.heapify(data)
print('pop:', heapq.heappop(data)) # pop: 13
print(data) # [27, 38, 49, 50, 76, 65, 97]
回顧堆排序算法
堆排序算法基本思想是：將無序序列建成一個堆，得到關(guān)鍵字最?。ɑ蜃畲蟮挠涗?；輸出堆頂?shù)淖钚?（大）值后，使剩余的 n-1 個元素 重又建成一個堆，則可得到n個元素的次小值 ；重復(fù)執(zhí)行，得到一個有序序列，這個就是堆排序的過程。
堆排序需要解決兩個問題：
- 如何由一個無序序列建立成一個堆？
- 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？
- 新添加元素和，如何調(diào)整堆？
先來看看第二個問題的解決方法。采用的方法叫“篩選”，當(dāng)輸出堆頂元素之后，就將堆中最后一個元素代替之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較 ，并與其中小者進行交換；重復(fù)上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。
如上圖所示，當(dāng)堆頂 13 輸出后，將堆中末尾的 97 替代為堆頂，然后堆頂與它的子節(jié)點 38 和 27 中的小者交換；元素 97 在新的位置上在和它的子節(jié)點 65 和 49 中的小者交換；直到元素97成為葉節(jié)點，就得到了新的堆。這個過程也叫 下沉 。
讓堆中位置為 pos 元素進行下沉的如下：
def heapdown(heap, pos): endpos = len(heap) while pos < endpos: lchild = 2 * pos + 1 rchild = 2 * pos + 2 if lchild >= endpos: # 如果pos已經(jīng)是葉節(jié)點，退出循環(huán) break childpos = lchild # 假設(shè)要交換的節(jié)點是左節(jié)點 if rchild < endpos and heap[childpos] > heap[rchild]: childpos = rchild if heap[pos] < heap[childpos]: # 如果節(jié)點比子節(jié)點都小，退出循環(huán) break heap[pos], heap[childpos] = heap[childpos], heap[pos] # 交換 pos = childpos
再來看看如何解決第三個問題：新添加元素和，如何調(diào)整堆？這個的方法正好與 下沉 相反，首先將新元素放置列表的最后，然后新元素與其父節(jié)點比較，若比父節(jié)點小，與父節(jié)點交換；重復(fù)過程直到比父節(jié)點大或到根節(jié)點。這個過程使得元素從底部不斷上升，從下至上恢復(fù)堆的順序，稱為 上浮 。
將位置為 pos 進行上浮的代碼為：
def heapup(heap, startpos, pos): # 如果是新增元素，startpos 傳入 0 while pos > startpos: parentpos = (pos - 1) // 2 if heap[pos] < heap[parentpos]: heap[pos], heap[parentpos] = heap[parentpos], heap[pos] pos = parentpos else: break
第一個問題：如何由一個無序序列建立成一個堆？從無序序列的第 n/2 個元素 （即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點 ）起 ，至第一個元素止，依次進行下沉：
for i in reversed(range(len(data) // 2)): heapdown(data, i)
heapq 源碼分析
添加新元素到堆中的 heappush() 函數(shù)：
def heappush(heap, item): """Push item onto heap, maintaining the heap invariant.""" heap.append(item) _siftdown(heap, 0, len(heap)-1)
把目標(biāo)元素放置列表最后，然后進行上浮。盡管它命名叫 down ,但這個過程是上浮的過程，這個命名也讓我困惑，后來我才知道它是因為元素的索引不斷減小，所以命名 down 。下沉的過程它也就命名為 up 了。
def _siftdown(heap, startpos, pos): newitem = heap[pos] # Follow the path to the root, moving parents down until finding a place # newitem fits. while pos > startpos: parentpos = (pos - 1) >> 1 parent = heap[parentpos] if newitem < parent: heap[pos] = parent pos = parentpos continue break heap[pos] = newitem
一樣是通過 newitem 不斷與父節(jié)點比較。不一樣的是這里缺少了元素交換的過程，而是計算出新元素最后所在的位置 pos 并進行的賦值。顯然這是優(yōu)化后的代碼，減少了不斷交換元素的冗余過程。
再來看看輸出堆頂元素的函數(shù) heappop():
def heappop(heap): """Pop the smallest item off the heap, maintaining the heap invariant.""" lastelt = heap.pop() # raises appropriate IndexError if heap is empty if heap: returnitem = heap[0] heap[0] = lastelt _siftup(heap, 0) return returnitem return lastelt
通過 heap.pop() 獲得列表中的最后一個元素，然后替換為堆頂 heap[0] = lastelt ，再進行下沉：
def _siftup(heap, pos): endpos = len(heap) startpos = pos newitem = heap[pos] # Bubble up the smaller child until hitting a leaf. childpos = 2*pos + 1 # 左節(jié)點，默認(rèn)替換左節(jié)點 while childpos < endpos: # Set childpos to index of smaller child. rightpos = childpos + 1 # 右節(jié)點 if rightpos < endpos and not heap[childpos] < heap[rightpos]: childpos = rightpos # 當(dāng)右節(jié)點比較小時，應(yīng)交換的是右節(jié)點 # Move the smaller child up. heap[pos] = heap[childpos] pos = childpos childpos = 2*pos + 1 # The leaf at pos is empty now. Put newitem there, and bubble it up # to its final resting place (by sifting its parents down). heap[pos] = newitem _siftdown(heap, startpos, pos)
這邊的代碼將準(zhǔn)備要下沉的元素視為新元素 newitem ，將其當(dāng)前的位置 pos 視為空位置，由其子節(jié)點中的小者進行取代，反復(fù)如此，最后會在葉節(jié)點留出一個位置，這個位置放入 newitem ，再讓新元素進行上浮。
再來看看讓無序數(shù)列重排成堆的 heapify() 函數(shù)：
def heapify(x): """Transform list into a heap, in-place, in O(len(x)) time.""" n = len(x) for i in reversed(range(n//2)): _siftup(x, i)
這部分就和理論上的一致，從最后一個非葉節(jié)點 (n // 2) 到根節(jié)點為止，進行下沉。
總結(jié)
堆排序結(jié)合圖來理解還是比較好理解的。這種數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊列（標(biāo)準(zhǔn)庫Queue的優(yōu)先隊列用的就是堆）。 heapq 模塊中還有很多其他 heapreplace ，heappushpop 等大體上都很類似。
好了，以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。
相關(guān)文章
Python對象與json數(shù)據(jù)的轉(zhuǎn)換問題實例詳解
JSON(JavaScript?Object?Notation)?是一種輕量級的數(shù)據(jù)交換格式，很受廣大用戶喜愛，今天通過本文給大家介紹Python對象與json數(shù)據(jù)的轉(zhuǎn)換問題,需要的朋友可以參考下2022-07-07
這篇文章主要介紹了Python簡單生成隨機數(shù)的方法,結(jié)合實例形式分析了Python基于random模塊生成隨機數(shù)的相關(guān)操作技巧,需要的朋友可以參考下2018-03-03
Python 數(shù)據(jù)處理更容易的12個輔助函數(shù)總結(jié)
Python的產(chǎn)生似乎就是專門用來處理數(shù)據(jù)的，順理成章的成為大數(shù)據(jù)的主流語言，本文介紹十二個函數(shù)輔助你更容易更便捷的用Python進行數(shù)據(jù)處理2021-11-11
這篇文章主要介紹了基于PyQt5完成的PDF拆分功能,本文介紹的pdf拆分功能還有一些待完善地方，例如可增加預(yù)覽功能，實現(xiàn)每頁預(yù)覽，以及如何實現(xiàn)多條件拆分，需要的朋友可以參考下2022-06-06
本文主要介紹了Python稀疏矩陣scipy.sparse包使用詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
這篇文章主要為大家詳細(xì)介紹了如何利用Python實現(xiàn)生成日報的功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-06-06
成功解決ValueError:?Supported?target?types?are:('binary
本文給大家分享成功解決ValueError:?Supported?target?types?are:('binary',?'multiclass').?Got?'continuous'?instead.的錯誤問題,需要的朋友可以參考下2023-03-03
本文主要介紹了新版selenium4.0 + Python使用詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
在Python中，字典是一種無序且可變的數(shù)據(jù)類型，用于存儲鍵值對數(shù)據(jù)，字典可以根據(jù)鍵（key）來快速檢索對應(yīng)的值，相比于其他類型的容器，如列表（List）、元組等，字典具有更高效的查找和插入性能，因此在Python編程中被廣泛使用2023-06-06
這篇文章主要介紹了matplotlib對象拾取事件處理的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01