什么是堆

堆（heap），是一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。它通常被看作一棵樹的數(shù)組對象。在隊列中，調(diào)度程序反復(fù)提取隊列中的第一個作業(yè)并運行，因為實際情況中某些時間較短的任務(wù)卻可能需要等待很長時間才能開始執(zhí)行，或者某些不短小、但很重要的作業(yè)，同樣應(yīng)當(dāng)擁有優(yōu)先權(quán)。而堆就是為了解決此類問題而設(shè)計的數(shù)據(jù)結(jié)構(gòu)。

二叉堆是一種特殊的堆，二叉堆是完全二叉樹或者近似完全二叉樹，二叉堆滿足堆特性：父節(jié)點的鍵值總是保持固定的序關(guān)系于任何一個子節(jié)點的鍵值，且每個節(jié)點的左子樹和右子樹都是一個二叉堆。

當(dāng)父節(jié)點的鍵值總是大于任何一個子節(jié)點的鍵值時為最大堆，當(dāng)父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。

為了更加形象，我們常用帶數(shù)字的圓圈和線條來表示二叉堆等，但其實都是用數(shù)組來表示的。如果根節(jié)點在數(shù)組中的位置是1，第n個位置的子節(jié)點則分別在2n和2n 1位置上。

如下圖所描的，第2個位置的子節(jié)點在4和5，第4個位置的子節(jié)點在8和9。所以我們獲得父節(jié)點和子節(jié)點的方式如下：

PARENT(i)

1 return 小于或等于i/2的最大整數(shù)

LEFT-CHILD(i)

1 return 2i

RIGHT-CHILD(i)

1 return 2i 1

假定表示堆的數(shù)組為A，那么A.length通常給出數(shù)組元素的個數(shù)，A.heap?size表示有多少個堆元素存儲在該數(shù)組中。這句話略帶拗口，也就是說數(shù)組A[1...A.length]可能都有數(shù)據(jù)存放，但只有A[1...A.heap?size]中存放的數(shù)據(jù)才是堆中的有效數(shù)據(jù)。毫無疑問0≤A.heap?size≤A.length。

最大堆除了根以外所有結(jié)點i都滿足：A[PARENT(i)]≥A[i]。

最小堆除了根以外所有結(jié)點i都滿足：A[PARENT(i)]≤A[i]。

一個堆中結(jié)點的高度是該結(jié)點到葉借點最長簡單路徑上邊的數(shù)目，如上圖所示編號為4的結(jié)點的高度為1，編號為2的結(jié)點的高度為2，樹的高度就是3。

包含n個元素的隊可以看作一顆完全二叉樹，那么該堆的高度是Θ(lgn)。

通過MAX-HEAPIFY維護最大堆

程序中，不可能所有的堆都天生就是最大堆，為了更好的使用堆這一數(shù)據(jù)結(jié)構(gòu)，我們可能要人為地構(gòu)造最大堆。

如何將一個雜亂排序的堆重新構(gòu)造成最大堆，它的主要思路是：

從上往下，將父節(jié)點與子節(jié)點以此比較。如果父節(jié)點最大則進行下一步循環(huán)，如果子節(jié)點更大，則將子節(jié)點與父節(jié)點位置互換，并進行下一步循環(huán)。注意父節(jié)點要與兩個子節(jié)點都進行比較。

如上圖說描述的，這里從結(jié)點為2開始做運算。先去l為4，r為5，將其與父節(jié)點做比較，發(fā)現(xiàn)左子節(jié)點比父節(jié)點更大。因此將它們做交換，設(shè)4為最大的結(jié)點，并繼續(xù)以結(jié)點4開始做下一步運算。

因此可以給出偽代碼如下：

MAX-HEAPIFY(A,i)

1 l=LEFT-CHILD(i)

2 r=RIGHT-CHILD(i)

3 if l<=A.heap-size and A[l]>A[i]

4 largest=l

5 else

6 largest=i

7 if r<=A.heap-size and A[r]>A[largest]

8 largest=r

9 if largest != i

10 exchange A[i] with A[largest]

11 MAX-HEAPIFY(A,largest)

在以上這些步驟中，調(diào)整A[i]、A[l]、A[r]的關(guān)系的時間代價為Θ(1)，再加上一棵以i的子節(jié)點為根結(jié)點的子樹上運行MAX-HEAPIFY的時間代價（注意此處的遞歸不一定會發(fā)生，此處只是假設(shè)其發(fā)生）。因為每個子節(jié)點的子樹的大小至多為2n/3（最壞情況發(fā)生在樹的底層恰好半滿的時候）。因此MAX-HEAPIFY過程的運行時間為：

T(n)≤T(2n/3) Θ(1)

也就是：

T(n)=O(lgn)

通過BUILD-MAX-HEAP構(gòu)建最大堆

前面我們通過自頂向下的方式維護了一個最大堆，這里將通過自底向上的方式通過MAX-HEAPIFY將一個n=A.length的數(shù)組A[1...n]轉(zhuǎn)換成最大堆。

回顧一下上面的圖示，其總共有9個結(jié)點，取小于或等于9/2的最大整數(shù)為4，從4 1，4 2，一直到n都是該樹的葉子結(jié)點，你發(fā)現(xiàn)了么？這對任意n都是成立的哦。

因此這里我們就要從4開始不斷的調(diào)用MAX-HEAPIFY(A,i)來構(gòu)建最大堆。

為什么會有這一思路呢？

原因是既然我們知道了哪些結(jié)點是葉子結(jié)點，從最后一個非葉子結(jié)點（這里是4）開始，一次調(diào)用MAX-HEAPIFY函數(shù)，就會將該結(jié)點與葉子結(jié)點做相應(yīng)的調(diào)整，這其實也就是一個遞歸的過程。

圖示已經(jīng)這么清晰了，就直接上偽代碼咯。

BUILD-MAX-HEAP(A)

1 A.heap-size=A.length

2 for i=小于或等于A.length/2的最大整數(shù) downto 1

3 MAX-HEAPIFY(A,i)

通過HEAPSORT進行堆排序算法

所謂的堆排序算法，先通過前面的BUILD-MAX-HEAP將輸入數(shù)組A[1...n]建成最大堆，其中n=A.length。而數(shù)組中的元素總在根結(jié)點A[1]中，通過把它與A[n]進行互換，就能將該元素放到正確的位置。

如何讓原來根的子結(jié)點仍然是最大堆呢，可以通過從堆中去掉結(jié)點n，而這可以通過減少A.heap?size來間接的完成。但這樣一來新的根節(jié)點就違背了最大堆的性質(zhì)，因此仍然需要調(diào)用MAX-HEAPIFY(A,1)，從而在A[1...n?1]上構(gòu)造一個新的最大堆。

通過不斷重復(fù)這一過程，知道堆的大小從n?1一直降到2即可。

上圖的演進方式主要有兩點：

1）將A[1]和A[i]互換，i從A.length一直遞減到2

2）不斷調(diào)用MAX-HEAPIFY(A,1)對剩余的整個堆進行重新構(gòu)建

一直到最后堆已經(jīng)不存在了。

HEAPSORT(A)

1 BUILD-MAX-HEAP(A)

2 for i=A.length downto 2

3 exchange A[1] with A[i]

4 A.heap-size=A.heap-size-1

5 MAX-HEAPIFY(A,1)

優(yōu)先隊列

下一篇博文我們就會介紹大名鼎鼎的快排，快速排序啦，歡迎童鞋們預(yù)定哦~

話說堆排序雖然性能上不及快速排序，但作為一個盡心盡力的數(shù)據(jù)結(jié)構(gòu)而言，其可謂業(yè)界良心吶。它還為我們提供了傳說中的“優(yōu)先隊列”。

優(yōu)先隊列（priority queue）和堆一樣，堆有最大堆和最小堆，優(yōu)先隊列也有最大優(yōu)先隊列和最小優(yōu)先隊列。

優(yōu)先隊列是一種用來維護由一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)，其中每個元素都有一個相關(guān)的值，稱之為關(guān)鍵字（key）。

一個最大優(yōu)先隊列支持一下操作：

MAXIMUM(S)：返回S中有著最大鍵值的元素。

EXTRACT?MAX(S)：去掉并返回S中的具有最大鍵字的元素。
INCREASE?KEY(S,x,a)：將元素x的關(guān)鍵字值增加到a，這里假設(shè)a的值不小于x的原關(guān)鍵字值。
INSERT(S,x)：將元素x插入集合S中，這一操作等價于S=S∪{x}。

這里來舉一個最大優(yōu)先隊列的示例，我曾在關(guān)于“50% CPU 占有率”題目的內(nèi)容擴展 這篇博文中簡單介紹過Windows的系統(tǒng)進程機制。

這里以圖片的形式簡單的貼出來如下：

在用堆實現(xiàn)優(yōu)先隊列時，需要在堆中的每個元素里存儲對應(yīng)對象的句柄（handle）。句柄的準(zhǔn)確含義依賴于具體的應(yīng)用程序，可以是指針，也可以是整型數(shù)。

在堆的操作過程中，元素會改變其在數(shù)組中的位置，因此在具體實現(xiàn)中，在重新確定堆元素位置時，就自然而然地需要改變其在數(shù)組中的位置。

一、前面的MAXIMUM(S)過程其實很簡單，完全可以在Θ(1)時間內(nèi)完成，因為只需要返回數(shù)組的第一個元素就可以呀，它已經(jīng)是最大優(yōu)先隊列了嘛。

HEAP-MAXIMUM(A)

1 return A[1]

二、EXTRACT?MAX(S)就稍顯復(fù)雜了一點，它的時間復(fù)雜度是O(lgn)，因為這里面除了MAX-HEAPIFY(A,1)以外，其他的操作都是常量時間的。

HEAP-EXTRACT-MAX(A)

1 if A.heap-size < 1

2 error '堆下溢'

3 max=A[1]

4 A[1]=A[A.heap-size]

5 A.heap-size=A.heap-size-1

6 MAX-HEAPIFY(A,1)

7 return max

三、INCREASE?KEY(S,x,a)需要將一個大于元素x原有關(guān)鍵字值的a加到元素x上。

和上一個函數(shù)一樣，首先判斷a知否比原有的關(guān)鍵字更大。

然后就是老辦法了，不斷的將該結(jié)點與父結(jié)點做對比，如果父結(jié)點更小，那么就將他們進行對換。

相信有圖示會更加清楚，于是……再來一張圖。

HEAP-INCREASE-KEY(A,i,key)

1 if key < A[i]

2 error '新關(guān)鍵字值比當(dāng)前關(guān)鍵字值更小'

3 A[i]=key

4 while i>1 and A[PARENT(i)] < A[i]

5 exchange A[i] with A[PARENT(I)]

6 i=PARENT(i)

在包含n個元素的堆上，HEAP-INCREASE-KEY的運行時間就是O(lgn)了。因為在第3行做了關(guān)鍵字更新的結(jié)點到根結(jié)點的路徑長度為O(lgn)。

四、INSERT(S,x)首先通過一個特殊的關(guān)鍵字（比如這里的-10000擴展）結(jié)點來擴展最大堆，然后調(diào)用HEAP-INCREASE-KEY來為新的結(jié)點設(shè)置對應(yīng)的關(guān)鍵字，同時保持最大堆的性質(zhì)。

MAX-HEAP-INSERT(A,key)

1 A.heap-size=A.heap-sieze 1

2 A[A.heap-size]=-10000

3 HEAP-INCREASE-KEY(A,A.hep-size,key)

在包含n個元素的堆上，MAX-HEAP-INSERT的運行時間就是O(lgn)了。因為這個算法相對于上一個算法，除了HEAP-INCREASE-KEY之外就都是常量的運行時間了，而HEAP-INCREASE-KEY的運行時間我們在上一部分已經(jīng)講過了。

總而言之，在一個包含n個元素的堆中，所有優(yōu)先隊列的操作時間都不會大于O(lgn)。