## heapq 堆（heap），是一種數據結構。用維基百科中的說明： > 堆（英語：heap)，是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。 對于這個新的概念，讀者不要感覺心慌意亂或者恐懼，因為它本質上不是新東西，而是在我們已經熟知的知識基礎上的擴展。 堆的實現是通過構造二叉堆，也就是一種二叉樹。 ### [](https://github.com/qiwsir/StarterLearningPython/blob/master/223.md#基本知識)基本知識 這是一顆在蘇州很常見的香樟樹，馬路兩邊、公園里隨處可見。 [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22301.jpg) 但是，在編程中，我們常說的樹通常不是上圖那樣的，而是這樣的： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22302.jpg) 跟真實現實生活中看到的樹反過來，也就是“根”在上面。為什么這樣呢？我想主要是畫著更方便吧。但是，我覺這棵樹，是完全寫實的作品。我本人做為一名隱姓埋名多年的抽象派畫家，不喜歡這樣的樹，我畫出來的是這樣的： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22303.jpg) 這棵樹有兩根枝杈，可不要小看這兩根枝杈哦，《道德經》上不是說“一生二，二生三，三生萬物”。一就是下面那個干，二就是兩個枝杈，每個枝杈還可以看做下一個一，然后再有兩個枝杈，如此不斷重復（這簡直就是遞歸呀），就成為了一棵大樹。 我的確很佩服我自己的后現代抽象派的作品。但是，我更喜歡把這棵樹畫成這樣： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22304.jpg) 并且給它一個正規的名字：二叉樹 [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22305.jpg) 這個也是二叉樹，完全脫胎于我所畫的后現代抽象主義作品。但是略有不同，這幅圖在各個枝杈上顯示的是數字。這種類型的“樹”就編程語言中所說的二叉樹，維基百科曰： > 在計算機科學中，二叉樹（英語：Binary tree）是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。 在上圖的二叉樹中，最頂端的那個數字就相當于樹根，也就稱作“根”。每個數字所在位置成為一個節點，每個節點向下分散出兩個“子節點”。就上圖的二叉樹，在最后一層，并不是所有節點都有兩個子節點，這類二叉樹又稱為完全二叉樹（Complete Binary Tree），也有的二叉樹，所有的節點都有兩個子節點，這類二叉樹稱作滿二叉樹（Full Binarry Tree)，如下圖： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22306.jpg) 下面討論的對象是實現二叉堆就是通過二叉樹實現的。其應該具有如下特點： * 節點的值大于等于（或者小于等于）任何子節點的值。 * 節點左子樹和右子樹是一個二叉堆。如果父節點的值總大于等于任何一個子節點的值，其為最大堆；若父節點值總小于等于子節點值，為最小堆。上面圖示中的完全二叉樹，就表示一個最小堆。 堆的類型還有別的，如斐波那契堆等，但很少用。所以，通常就將二叉堆也說成堆。下面所說的堆，就是二叉堆。而二叉堆又是用二叉樹實現的。 ### [](https://github.com/qiwsir/StarterLearningPython/blob/master/223.md#堆的存儲)堆的存儲 堆用列表（有的語言中成為數組）來表示。如下圖所示： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22307.jpg) 從圖示中可以看出，將邏輯結構中的樹的節點數字依次填入到存儲結構中。看這個圖，似乎是列表中按照順序進行排列似的。但是，這僅僅由于那個樹的特點造成的，如果是下面的樹： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22308.jpg) 如果將上面的邏輯結構轉換為存儲結構，讀者就能看出來了，不再是按照順序排列的了。 關于堆的各種，如插入、刪除、排序等，本節不會專門講授編碼方法，讀者可以參與有關資料。但是，下面要介紹如何用python中的模塊heapq來實現這些操作。 ### [](https://github.com/qiwsir/StarterLearningPython/blob/master/223.md#heapq模塊)heapq模塊 heapq中的heap是堆，q就是queue（隊列）的縮寫。此模塊包括： ~~~ >>> import heapq >>> heapq.__all__ ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop'] ~~~ 依次查看這些函數的使用方法。 **heappush(heap, x)**：將x壓入對heap（這是一個列表） ~~~ Help on built-in function heappush in module _heapq: heappush(...) heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant. >>> import heapq >>> heap = [] >>> heapq.heappush(heap, 3) >>> heapq.heappush(heap, 9) >>> heapq.heappush(heap, 2) >>> heapq.heappush(heap, 4) >>> heapq.heappush(heap, 0) >>> heapq.heappush(heap, 8) >>> heap [0, 2, 3, 9, 4, 8] ~~~ 請讀者注意我上面的操作，在向堆增加數值的時候，我并沒有嚴格按照什么順序，是隨意的。但是，當我查看堆的數據時，顯示給我的是一個有一定順序的數據結構。這種順序不是按照從小到大，而是按照前面所說的完全二叉樹的方式排列。顯示的是存儲結構，可以把它還原為邏輯結構，看看是不是一顆二叉樹。 [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22309.jpg) 由此可知，利用`heappush()`函數將數據放到堆里面之后，會自動按照二叉樹的結構進行存儲。 **heappop(heap)**：刪除最小元素 承接上面的操作： ~~~ >>> heapq.heappop(heap) 0 >>> heap [2, 4, 3, 9, 8] ~~~ 用`heappop()`函數，從heap堆中刪除了一個最小元素，并且返回該值。但是，這時候的heap顯示順序，并非簡單地將0去除，而是按照完全二叉樹的規范重新進行排列。 **heapify()**：將列表轉換為堆 如果已經建立了一個列表，利用`heapify()`可以將列表直接轉化為堆。 ~~~ >>> hl = [2, 4, 6, 8, 9, 0, 1, 5, 3] >>> heapq.heapify(hl) >>> hl [0, 3, 1, 4, 9, 6, 2, 5, 8] ~~~ 經過這樣的操作，列表hl就變成了堆（注意觀察堆的順序，和列表不同），可以對hl（堆）使用heappop()或者heappush()等函數了。否則，不可。 ~~~ >>> heapq.heappop(hl) 0 >>> heapq.heappop(hl) 1 >>> hl [2, 3, 5, 4, 9, 6, 8] >>> heapq.heappush(hl, 9) >>> hl [2, 3, 5, 4, 9, 6, 8, 9] ~~~ 不要認為堆里面只能放數字，之所以用數字，是因為對它的邏輯結構比較好理解。 ~~~ >>> heapq.heappush(hl, "q") >>> hl [2, 3, 5, 4, 9, 6, 8, 9, 'q'] >>> heapq.heappush(hl, "w") >>> hl [2, 3, 5, 4, 9, 6, 8, 9, 'q', 'w'] ~~~ **heapreplace()** 是heappop()和heappush()的聯合，也就是刪除一個，同時加入一個。例如： ~~~ >>> heap [2, 4, 3, 9, 8] >>> heapq.heapreplace(heap, 3.14) 2 >>> heap [3, 4, 3.14, 9, 8] ~~~ 先簡單羅列關于對的幾個常用函數。那么堆在編程實踐中的用途在哪方面呢？主要在排序上。一提到排序，讀者肯定想到的是sorted()或者列表中的sort()，不錯，這兩個都是常用的函數，而且在一般情況下已經足夠使用了。如果再使用堆排序，相對上述方法應該有優勢。 堆排序的優勢不僅更快，更重要的是有效地使用內存，當然，另外一個也不同忽視，就是簡單易用。比如前面操作的，刪除數列中最小的值，就是在排序基礎上進行的操作。 ## [](https://github.com/qiwsir/StarterLearningPython/blob/master/223.md#deque模塊)deque模塊 有這樣一個問題：一個列表，比如是`[1,2,3]`，我打算在最右邊增加一個數字。 這也太簡單了，不就是用`append()`這個內建函數，追加一個嗎？ 這是簡單，我要得寸進尺，能不能在最左邊增加一個數字呢？ 這個嘛，應該有辦法。不過得想想了。讀者在向下閱讀的時候，能不能想出一個方法來？ ~~~ >>> lst = [1, 2, 3] >>> lst.append(4) >>> lst [1, 2, 3, 4] >>> nl = [7] >>> nl.extend(lst) >>> nl [7, 1, 2, 3, 4] ~~~ 你或許還有別的方法。但是，python為我們提供了一個更簡單的模塊，來解決這個問題。 ~~~ >>> from collections import deque ~~~ 這次用這種引用方法，因為collections模塊中東西很多，我們只用到deque。 ~~~ >>> lst [1, 2, 3, 4] ~~~ 還是這個列表。試試分別從右邊和左邊增加數 ~~~ >>> qlst = deque(lst) ~~~ 這是必須的，將列表轉化為deque。deque在漢語中有一個名字，叫做“雙端隊列”（double-ended queue）。 ~~~ >>> qlst.append(5) #從右邊增加 >>> qlst deque([1, 2, 3, 4, 5]) >>> qlst.appendleft(7) #從左邊增加 >>> qlst deque([7, 1, 2, 3, 4, 5]) ~~~ 這樣操作多么容易呀。繼續看刪除： ~~~ >>> qlst.pop() 5 >>> qlst deque([7, 1, 2, 3, 4]) >>> qlst.popleft() 7 >>> qlst deque([1, 2, 3, 4]) ~~~ 刪除也分左右。下面這個，請讀者仔細觀察，更有點意思。 ~~~ >>> qlst.rotate(3) >>> qlst deque([2, 3, 4, 1]) ~~~ rotate()的功能是將[1, 2, 3, 4]的首位連起來，你就想象一個圓環，在上面有1,2,3,4幾個數字。如果一開始正對著你的是1，依順時針方向排列，就是從1開始的數列，如下圖所示： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22310.jpg) 經過`rotate()`，這個環就發生旋轉了，如果是`rotate(3)`，表示每個數字按照順時針方向前進三個位置，于是變成了： [](https://github.com/qiwsir/StarterLearningPython/blob/master/2images/22311.jpg) 請原諒我的后現代注意超級抽象派作圖方式。從圖中可以看出，數列變成了[2, 3, 4, 1]。rotate()作用就好像在撥轉這個圓環。 ~~~ >>> qlst deque([3, 4, 1, 2]) >>> qlst.rotate(-1) >>> qlst deque([4, 1, 2, 3]) ~~~ 如果參數是復數，那么就逆時針轉。 在deque中，還有extend和extendleft方法。讀者可自己調試。