起步

這是一個相當實用的內置模塊，但是很多人竟然不知道他的存在——筆者也是今天偶然看到的，哎……盡管如此，還是改變不了這個模塊好用的事實

heapq 模塊實現了適用于Python列表的最小堆排序算法。

堆是一個樹狀的數據結構，其中的子節點都與父母排序順序關系。因為堆排序中的樹是滿二叉樹，因此可以用列表來表示樹的結構，使得元素 N 的子元素位于 2N + 1 和 2N + 2 的位置（對于從零開始的索引）。

本文內容將分為三個部分，第一個部分簡單介紹 heapq 模塊的使用；第二部分回顧堆排序算法；第三部分分析heapq中的實現。

heapq 的使用

創建堆有兩個基本的方法：heappush() 和 heapify()，取出堆頂元素用 heappop()。

heappush() 是用來向已有的堆中添加元素，一般從空列表開始構建：

import heapqdata = [97, 38, 27, 50, 76, 65, 49, 13]heap = []for n in data: heapq.heappush(heap, n)print('pop:', heapq.heappop(heap)) # pop: 13print(heap) # [27, 50, 38, 97, 76, 65, 49]

如果數據已經在列表中，則使用 heapify() 進行重排：

import heapqdata = [97, 38, 27, 50, 76, 65, 49, 13]heapq.heapify(data)print('pop:', heapq.heappop(data)) # pop: 13print(data) # [27, 38, 49, 50, 76, 65, 97]

回顧堆排序算法

堆排序算法基本思想是：將無序序列建成一個堆，得到關鍵字最小（或最大的記錄；輸出堆頂的最小 （大）值后，使剩余的 n-1 個元素 重又建成一個堆，則可得到n個元素的次小值 ；重復執行，得到一個有序序列，這個就是堆排序的過程。

堆排序需要解決兩個問題：

先來看看第二個問題的解決方法。采用的方法叫“篩選”，當輸出堆頂元素之后，就將堆中最后一個元素代替之；然后將根結點值與左、右子樹的根結點值進行比較 ，并與其中小者進行交換；重復上述操作，直至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調整過程為“篩選”。