heapq

堆（heap），是一種數(shù)據(jù)結(jié)構(gòu)。用維基百科中的說(shuō)明：

堆（英語(yǔ)：heap)，是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象。

對(duì)于這個(gè)新的概念，讀者不要感覺(jué)心慌意亂或者恐懼，因?yàn)樗举|(zhì)上不是新東西，而是在我們已經(jīng)熟知的知識(shí)基礎(chǔ)上的擴(kuò)展。

堆的實(shí)現(xiàn)是通過(guò)構(gòu)造二叉堆，也就是一種二叉樹。

基本知識(shí)

這是一顆在蘇州很常見的香樟樹，馬路兩邊、公園里隨處可見。

但是，在編程中，我們常說(shuō)的樹通常不是上圖那樣的，而是這樣的：

跟真實(shí)現(xiàn)實(shí)生活中看到的樹反過(guò)來(lái)，也就是“根”在上面。為什么這樣呢？我想主要是畫著更方便吧。但是，我覺(jué)這棵樹，是完全寫實(shí)的作品。我本人做為一名隱姓埋名多年的抽象派畫家，不喜歡這樣的樹，我畫出來(lái)的是這樣的：

這棵樹有兩根枝杈，可不要小看這兩根枝杈哦，《道德經(jīng)》上不是說(shuō)“一生二，二生三，三生萬(wàn)物”。一就是下面那個(gè)干，二就是兩個(gè)枝杈，每個(gè)枝杈還可以看做下一個(gè)一，然后再有兩個(gè)枝杈，如此不斷重復(fù)（這簡(jiǎn)直就是遞歸呀），就成為了一棵大樹。

我的確很佩服我自己的后現(xiàn)代抽象派的作品。但是，我更喜歡把這棵樹畫成這樣：

并且給它一個(gè)正規(guī)的名字：二叉樹

這個(gè)也是二叉樹，完全脫胎于我所畫的后現(xiàn)代抽象主義作品。但是略有不同，這幅圖在各個(gè)枝杈上顯示的是數(shù)字。這種類型的“樹”就編程語(yǔ)言中所說(shuō)的二叉樹，維基百科曰：

在計(jì)算機(jī)科學(xué)中，二叉樹（英語(yǔ)：Binary tree）是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實(shí)現(xiàn)二叉查找樹和二叉堆。

在上圖的二叉樹中，最頂端的那個(gè)數(shù)字就相當(dāng)于樹根，也就稱作“根”。每個(gè)數(shù)字所在位置成為一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)向下分散出兩個(gè)“子節(jié)點(diǎn)”。就上圖的二叉樹，在最后一層，并不是所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，這類二叉樹又稱為完全二叉樹（Complete Binary Tree），也有的二叉樹，所有的節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，這類二叉樹稱作滿二叉樹（Full Binarry Tree)，如下圖：

下面討論的對(duì)象是實(shí)現(xiàn)二叉堆就是通過(guò)二叉樹實(shí)現(xiàn)的。其應(yīng)該具有如下特點(diǎn)：

• 節(jié)點(diǎn)的值大于等于（或者小于等于）任何子節(jié)點(diǎn)的值。
• 節(jié)點(diǎn)左子樹和右子樹是一個(gè)二叉堆。如果父節(jié)點(diǎn)的值總大于等于任何一個(gè)子節(jié)點(diǎn)的值，其為最大堆；若父節(jié)點(diǎn)值總小于等于子節(jié)點(diǎn)值，為最小堆。上面圖示中的完全二叉樹，就表示一個(gè)最小堆。

堆的類型還有別的，如斐波那契堆等，但很少用。所以，通常就將二叉堆也說(shuō)成堆。下面所說(shuō)的堆，就是二叉堆。而二叉堆又是用二叉樹實(shí)現(xiàn)的。

堆的存儲(chǔ)

堆用列表（有的語(yǔ)言中成為數(shù)組）來(lái)表示。如下圖所示：

從圖示中可以看出，將邏輯結(jié)構(gòu)中的樹的節(jié)點(diǎn)數(shù)字依次填入到存儲(chǔ)結(jié)構(gòu)中?？催@個(gè)圖，似乎是列表中按照順序進(jìn)行排列似的。但是，這僅僅由于那個(gè)樹的特點(diǎn)造成的，如果是下面的樹：

如果將上面的邏輯結(jié)構(gòu)轉(zhuǎn)換為存儲(chǔ)結(jié)構(gòu)，讀者就能看出來(lái)了，不再是按照順序排列的了。

關(guān)于堆的各種，如插入、刪除、排序等，本節(jié)不會(huì)專門講授編碼方法，讀者可以參與有關(guān)資料。但是，下面要介紹如何用python中的模塊heapq來(lái)實(shí)現(xiàn)這些操作。

heapq模塊

heapq中的heap是堆，q就是queue（隊(duì)列）的縮寫。此模塊包括：

>>> import heapq
>>> heapq.__all__
['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']

依次查看這些函數(shù)的使用方法。

heappush(heap, x)：將x壓入對(duì)heap（這是一個(gè)列表）

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]

請(qǐng)讀者注意我上面的操作，在向堆增加數(shù)值的時(shí)候，我并沒(méi)有嚴(yán)格按照什么順序，是隨意的。但是，當(dāng)我查看堆的數(shù)據(jù)時(shí)，顯示給我的是一個(gè)有一定順序的數(shù)據(jù)結(jié)構(gòu)。這種順序不是按照從小到大，而是按照前面所說(shuō)的完全二叉樹的方式排列。顯示的是存儲(chǔ)結(jié)構(gòu)，可以把它還原為邏輯結(jié)構(gòu)，看看是不是一顆二叉樹。

由此可知，利用heappush()函數(shù)將數(shù)據(jù)放到堆里面之后，會(huì)自動(dòng)按照二叉樹的結(jié)構(gòu)進(jìn)行存儲(chǔ)。

heappop(heap)：刪除最小元素

承接上面的操作：

>>> heapq.heappop(heap)
0
>>> heap
[2, 4, 3, 9, 8]

用heappop()函數(shù)，從heap堆中刪除了一個(gè)最小元素，并且返回該值。但是，這時(shí)候的heap顯示順序，并非簡(jiǎn)單地將0去除，而是按照完全二叉樹的規(guī)范重新進(jìn)行排列。

heapify()：將列表轉(zhuǎn)換為堆

如果已經(jīng)建立了一個(gè)列表，利用heapify()可以將列表直接轉(zhuǎn)化為堆。

>>> hl = [2, 4, 6, 8, 9, 0, 1, 5, 3]
>>> heapq.heapify(hl)
>>> hl
[0, 3, 1, 4, 9, 6, 2, 5, 8]

經(jīng)過(guò)這樣的操作，列表hl就變成了堆（注意觀察堆的順序，和列表不同），可以對(duì)hl（堆）使用heappop()或者h(yuǎn)eappush()等函數(shù)了。否則，不可。

>>> 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]

不要認(rèn)為堆里面只能放數(shù)字，之所以用數(shù)字，是因?yàn)閷?duì)它的邏輯結(jié)構(gòu)比較好理解。

>>> 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()的聯(lián)合，也就是刪除一個(gè)，同時(shí)加入一個(gè)。例如：

>>> heap
[2, 4, 3, 9, 8]
>>> heapq.heapreplace(heap, 3.14)
2
>>> heap
[3, 4, 3.14, 9, 8]

先簡(jiǎn)單羅列關(guān)于對(duì)的幾個(gè)常用函數(shù)。那么堆在編程實(shí)踐中的用途在哪方面呢？主要在排序上。一提到排序，讀者肯定想到的是sorted()或者列表中的sort()，不錯(cuò)，這兩個(gè)都是常用的函數(shù)，而且在一般情況下已經(jīng)足夠使用了。如果再使用堆排序，相對(duì)上述方法應(yīng)該有優(yōu)勢(shì)。

堆排序的優(yōu)勢(shì)不僅更快，更重要的是有效地使用內(nèi)存，當(dāng)然，另外一個(gè)也不同忽視，就是簡(jiǎn)單易用。比如前面操作的，刪除數(shù)列中最小的值，就是在排序基礎(chǔ)上進(jìn)行的操作。

deque模塊

有這樣一個(gè)問(wèn)題：一個(gè)列表，比如是[1,2,3]，我打算在最右邊增加一個(gè)數(shù)字。

這也太簡(jiǎn)單了，不就是用append()這個(gè)內(nèi)建函數(shù)，追加一個(gè)嗎？

這是簡(jiǎn)單，我要得寸進(jìn)尺，能不能在最左邊增加一個(gè)數(shù)字呢？

這個(gè)嘛，應(yīng)該有辦法。不過(guò)得想想了。讀者在向下閱讀的時(shí)候，能不能想出一個(gè)方法來(lái)？

>>> lst = [1, 2, 3]
>>> lst.append(4)
>>> lst
[1, 2, 3, 4]
>>> nl = [7]
>>> nl.extend(lst)
>>> nl
[7, 1, 2, 3, 4]

你或許還有別的方法。但是，python為我們提供了一個(gè)更簡(jiǎn)單的模塊，來(lái)解決這個(gè)問(wèn)題。

>>> from collections import deque

這次用這種引用方法，因?yàn)閏ollections模塊中東西很多，我們只用到deque。

>>> lst
[1, 2, 3, 4]

還是這個(gè)列表。試試分別從右邊和左邊增加數(shù)

>>> qlst = deque(lst)

這是必須的，將列表轉(zhuǎn)化為deque。deque在漢語(yǔ)中有一個(gè)名字，叫做“雙端隊(duì)列”（double-ended queue）。

>>> qlst.append(5)        #從右邊增加
>>> qlst
deque([1, 2, 3, 4, 5])
>>> qlst.appendleft(7)    #從左邊增加
>>> qlst
deque([7, 1, 2, 3, 4, 5])

這樣操作多么容易呀。繼續(xù)看刪除：

>>> qlst.pop()
5
>>> qlst
deque([7, 1, 2, 3, 4])
>>> qlst.popleft()
7
>>> qlst
deque([1, 2, 3, 4])

刪除也分左右。下面這個(gè)，請(qǐng)讀者仔細(xì)觀察，更有點(diǎn)意思。

>>> qlst.rotate(3)
>>> qlst
deque([2, 3, 4, 1])

rotate()的功能是將[1, 2, 3, 4]的首位連起來(lái)，你就想象一個(gè)圓環(huán)，在上面有1,2,3,4幾個(gè)數(shù)字。如果一開始正對(duì)著你的是1，依順時(shí)針?lè)较蚺帕?，就是?開始的數(shù)列，如下圖所示：

經(jīng)過(guò)rotate()，這個(gè)環(huán)就發(fā)生旋轉(zhuǎn)了，如果是rotate(3)，表示每個(gè)數(shù)字按照順時(shí)針?lè)较蚯斑M(jìn)三個(gè)位置，于是變成了：

請(qǐng)?jiān)徫业暮蟋F(xiàn)代注意超級(jí)抽象派作圖方式。從圖中可以看出，數(shù)列變成了[2, 3, 4, 1]。rotate()作用就好像在撥轉(zhuǎn)這個(gè)圓環(huán)。

>>> qlst
deque([3, 4, 1, 2])
>>> qlst.rotate(-1)
>>> qlst
deque([4, 1, 2, 3])

如果參數(shù)是復(fù)數(shù)，那么就逆時(shí)針轉(zhuǎn)。

在deque中，還有extend和extendleft方法。讀者可自己調(diào)試。