紙上談兵: 堆 (heap)
作者：Vamei 出處：http://www.cnblogs.com/vamei 歡迎轉載，也請保留這段聲明。謝謝！
?
堆(heap)又被為優先隊列(priority queue)。盡管名為優先隊列，但堆并不是隊列。回憶一下，在隊列中，我們可以進行的限定操作是dequeue和enqueue。dequeue是按照進入隊列的先后順序來取出元素。而在堆中，我們不是按照元素進入隊列的先后順序取出元素的，而是按照元素的優先級取出元素。
這就好像候機的時候，無論誰先到達候機廳，總是頭等艙的乘客先登機，然后是商務艙的乘客，最后是經濟艙的乘客。每個乘客都有頭等艙、商務艙、經濟艙三種個鍵值(key)中的一個。頭等艙->商務艙->經濟艙依次享有從高到低的優先級。
再比如，封建社會的等級制度，也是一個堆。在這個堆中，國王、貴族、騎士和農民是從高到低的優先級。
封建等級
?
Linux內核中的調度器(scheduler)會按照各個進程的優先級來安排CPU執行哪一個進程。計算機中通常有多個進程，每個進程有不同的優先級(該優先級的計算會綜合多個因素，比如進程所需要耗費的時間，進程已經等待的時間，用戶的優先級，用戶設定的進程優先程度等等)。內核會找到優先級最高的進程，并執行。如果有優先級更高的進程被提交，那么調度器會轉而安排該進程運行。優先級比較低的進程則會等待。“堆”是實現調度器的理想數據結構。
(Linux中可以使用nice命令來影響進程的優先級)
?
堆的實現
堆的一個經典的實現是完全二叉樹(complete binary tree)。這樣實現的堆成為二叉堆(binary heap)。
完全二叉樹是增加了限定條件的二叉樹。假設一個二叉樹的深度為n。為了滿足完全二叉樹的要求，該二叉樹的前n-1層必須填滿，第n層也必須按照從左到右的順序被填滿，比如下圖:
為了實現堆的操作，我們額外增加一個要求:?任意節點的優先級不小于它的子節點。如果在上圖中，設定小的元素值享有高的優先級，那么上圖就符合該要求。
這類似于“疊羅漢”。疊羅漢最重要的一點，就是讓體重大的參與者站在最下面，讓體重小的參與者站在上面 (體重小，優先級高)。為了讓“堆”穩固，我們每次只允許最上面的參與者退出堆。也就是，每次取出的優先級最高的元素。
三個“疊羅漢”堆
?
我已經在排序算法簡介及其C實現中實際使用了堆。堆的主要操作是插入和刪除最小元素(元素值本身為優先級鍵值，小元素享有高優先級)。在插入或者刪除操作之后，我們必須保持該實現應有的性質: 1. 完全二叉樹 2. 每個節點值都小于或等于它的子節點。
?
在插入操作的時候，會破壞上述堆的性質，所以需要進行名為percolate_up的操作，以進行恢復。新插入的節點new放在完全二叉樹最后的位置，再和父節點比較。如果new節點比父節點小，那么交換兩者。交換之后，繼續和新的父節點比較…… 直到new節點不比父節點小，或者new節點成為根節點。這樣得到的樹，就恢復了堆的性質。
我們插入節點2:
插入
?
刪除操作只能刪除根節點。根節點刪除后，我們會有兩個子樹，我們需要基于它們重構堆。進行percolate_down的操作: 讓最后一個節點last成為新的節點，從而構成一個新的二叉樹。再將last節點不斷的和子節點比較。如果last節點比兩個子節點中小的那一個大，則和該子節點交換。直到last節點不大于任一子節點都小，或者last節點成為葉節點。
刪除根節點1。如圖:
刪除根節點
?
下面是代碼。與我們在二叉搜索樹中使用表不同，我們這里使用數組來表示完全二叉樹。數組下標為0的元素不用于儲存節點，而用于記錄完全二叉樹中元素的總數。
/* By Vamei Use an big array to implement heapDECLARE: int heap[MAXSIZE] in calling functionheap[0] : total nodes in the heapfor a node i, its children are i*2 and i*2+1 (if exists)its parent is i/2 */void insert(int new, int heap[])
{int childIdx, parentIdx;heap[0] = heap[0] + 1;heap[heap[0]] = new;/* recover heap property */percolate_up(heap);
}static void percolate_up(int heap[]) {int lightIdx, parentIdx;lightIdx = heap[0];parentIdx = lightIdx/2;/* lightIdx is root? && swap? */while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {/* swap */swap(heap + lightIdx, heap + parentIdx); lightIdx = parentIdx;parentIdx = lightIdx/2;}
}int delete_min(int heap[])
{int min;if (heap[0] < 1) {/* delete element from an empty heap */printf("Error: delete_min from an empty heap.");exit(1);}/* delete root move the last leaf to the root */min = heap[1];swap(heap + 1, heap + heap[0]);heap[0] -= 1;/* recover heap property */percolate_down(heap);return min;
}static void percolate_down(int heap[]) {int heavyIdx;int childIdx1, childIdx2, minIdx;int sign; /* state variable, 1: swap; 0: no swap */heavyIdx = 1;do {sign = 0;childIdx1 = heavyIdx*2;childIdx2 = childIdx1 + 1;if (childIdx1 > heap[0]) {/* both children are null */break; }else if (childIdx2 > heap[0]) {/* right children is null */minIdx = childIdx1;}else {minIdx = (heap[childIdx1] < heap[childIdx2]) ?childIdx1 : childIdx2;}if (heap[heavyIdx] > heap[minIdx]) {/* swap with child */swap(heap + heavyIdx, heap + minIdx);heavyIdx = minIdx;sign = 1;}} while(sign == 1);
} 你可以嘗試一下構建自己的main函數，測試相關的操作。
?
總結
堆，優先級
插入元素，刪除最大優先級元素
?
歡迎繼續閱讀“紙上談兵: 算法與數據結構”系列。
