第八章 堆 積 堆積（heap）是樹結構的第三種型態。堆積是一棵二元樹，其左右子樹節點的值均較其父母節點的值小。堆積的根節點值保證是該樹最大值。這中堆績稱為最大堆績。堆積的子樹可擺在左邊當左子樹，也可擺在右邊當右子樹，因此左右子樹俱有相同的性質。 堆積還有一個有趣的特性，就是以陣列實作較以連結串列實作佳。當以陣列實作堆積時，已知父母節點的註標（subscript）就可算出其左右子樹節點的註標，反之亦然。

Presentation on theme: "第八章 堆 積 堆積（heap）是樹結構的第三種型態。堆積是一棵二元樹，其左右子樹節點的值均較其父母節點的值小。堆積的根節點值保證是該樹最大值。這中堆績稱為最大堆績。堆積的子樹可擺在左邊當左子樹，也可擺在右邊當右子樹，因此左右子樹俱有相同的性質。 堆積還有一個有趣的特性，就是以陣列實作較以連結串列實作佳。當以陣列實作堆積時，已知父母節點的註標（subscript）就可算出其左右子樹節點的註標，反之亦然。"— Presentation transcript:

1 第八章 堆 積 堆積（heap）是樹結構的第三種型態。堆積是一棵二元樹，其左右子樹節點的值均較其父母節點的值小。堆積的根節點值保證是該樹最大值。這中堆績稱為最大堆績。堆積的子樹可擺在左邊當左子樹，也可擺在右邊當右子樹，因此左右子樹俱有相同的性質。 堆積還有一個有趣的特性，就是以陣列實作較以連結串列實作佳。當以陣列實作堆積時，已知父母節點的註標（subscript）就可算出其左右子樹節點的註標，反之亦然。 若父母節點的註標 i 從 0 開始計數時，則左子樹節點的註標為 2*i+1，右子樹節點的註標為 2*i+2。 若父母節點的註標 i 從 1 開始計數時，則左子樹節點的註標為 2*i，右子樹節點的註標為 2*i+1。 已知子女節點的註標也可算出其父母節點的註標，因此處理的效率相當高。

2 8.1 基本觀念 一棵堆積是一棵二元樹，俱備下列的特性： 1. 這棵樹是一棵完整或接近完整的二元樹。
2. 每一節點的鍵值大於或等於其子樹節點鍵值。 一棵完整的二元樹是每一層次（level）都佔滿，一棵接近完整的二元樹指其葉節點相差在一個層次以內。堆積如下圖所示。

3 三種堆積舉例 在上圖的兄弟節點裡，左節點有大於右節點者（13>9），左節點有小於右節點者（7<11，19<24），這對於前面章節說明過的二元搜尋樹是不允許的。注意上圖（c）是一棵接近完整的二元樹，第二層次是從左而右填滿的，這也是堆積的要求。

4 堆積有兩個基本的操作 對於堆積有兩個基本的操作：插入一個節點以及移除一個節點。雖然堆積是一棵樹，但對它執行遍訪、搜尋、列印的操作並無意義。要實作堆積的插入及移除節點操作，我們需要兩個演算法，再堆上（reheap up）以及再堆下（reheap down）。

5 8.1.1 再堆上作業 假想我們有一個 N 個元素的接近完整二元樹，其前面的 N-1 個元素均已滿足堆積的要求，但最後一個元素 N 卻不滿足堆積，換句話說只要第 N 個元素滿足堆積的要求，整個結構就是一個堆積了。再堆上作業將第 N 個元素往上堆，定位於正確的位置，使整個結構成為一個堆積。

6 26往上移動 上圖新元素 26 插入原來已成堆積的樹。最後的元素規定要擺在最右邊的。26 比它的父母節點 13 還大，違反堆積的規定，必須互換，因此就往上移動，如下圖所示。

7 26再往上移動 26 比它的父母節點 43 還小，就不必再移動，已經定到正確的位置了。這種再堆上使成堆積的作業稱為再堆上操作。

8 8.1.2 再堆下作業 再堆下作業事實上是再堆上的相反操作。舉例如下圖。

9 8.2 堆積實作 雖然堆積可以透過動態樹結構建立起來，但最常見的還是以陣列實作為宜。一個節點與其子女節點的關係可以計算出來，如下所述：
1. 若節點註標為 i（從0算起），則其子女節點的註標計算 如下： a). 左子女節點註標為 2*i+1 b). 右子女節點註標為 2*i+2 2. 若節點註標為 i（從0算起），則其父母節點的註標計算 如下：取 (i-1)/2 之整數部份。 3. 左子女節點註標為 j，右子女節點註標為 j+1。 右子女節點註標為 k，左子女節點註標為 k-1。 4. 設完整堆積元素數為 n，第一個葉節點為 (n/2) 之整數部份。最後的枝節點註標為 (n/2)-1 之整數部份。

10 堆積以樹及陣列表示 的註標為 2（從0算起），左子女節點 24 註標 為 2*2+1=5，右子女節點 20 註標為 2*2+2=6。 2. 9 的註標為 4（從0算起），其父母節點 57 的註標 為 (4-1)/2 整數部份為 1。 3. 總共有 7 個元素（n=7），第一個葉節點為 7/2 整數部份為 3。 4. 最後的枝節點 33 註標為 (n/2)-1=(7/2)-1=2。

11 8.3 堆積結構 struct heapTag { void **data; int last; int size;
int (*compare) (void *arg1, void *arg2); int maxsize; };

12 data指標變數的含意 這種結構就命名為 heapTag 結構。請注意 data 是 void 不定型態指標的指標，也就是說傳給此結構的資料本身是一個位址，此位址存於指標變數 *data 裡頭，此 *data 欄的位址卻存於 **data 指標變數裡頭，如下圖所示。

13 8.4 建立堆積結構 struct heapTag *heapCreate(int maxsize,
int (*compare) (void *arg1, void *arg2)) { struct heapTag *heap; heap = malloc(sizeof(struct heapTag)); if (heap == NULL) return NULL; heap->last = -1; heap->size = 0; heap->compare = compare; heap->maxsize = (int)pow(2,ceil(log2(maxsize)))-1; heap->data = (void*) calloc( heap->maxsize, sizeof(void *)); return heap; } 8.4 建立堆積結構

14 建立堆積結構 需要提供兩個引數，第一個是最大容量之元素個數 maxsize，第二個是比較的函式名稱 compare。首先取得一塊 heapTag 結構的 heap 記憶體，設定 heap->last 為 -1，heap->size 為 0，heap->mazsize 最大容量為 2 的 log10(maxsize)/log10(2) 次方值再減一，例如 mazsize 引數值為 16，那麼 heap->maxsize 的值為 2 的 4 次方再減一，為 7。

15 建立堆積結構

16 8.5 插入堆積 int heapInsert(struct heapTag *heap, void *dataptr) {
if (heap->size == 0) heap->size = 1; heap->last = 0; heap->data[heap->last] = dataptr; return 1; } if (heap->last == heap->maxsize - 1) return 0; ++(heap->last); ++(heap->size); ReheapUp(heap, heap->last); 8.5 插入堆積

17 void ReheapUp(struct heapTag *heap, int child)
{ int parent; void **data, **temp; if (child != 0) data = heap->data; parent = (child - 1)/ 2; if (heap->compare(data[child],data[parent])>0) temp=data[parent]; data[parent]=data[child]; data[child]=temp; ReheapUp (heap, parent); } return;

18 8.6 從堆積移除節點 int heapRemove(struct heapTag *heap, void **dataptr) {
if (heap->size == 0) return 0; *dataptr = heap->data[0]; heap->data[0] = heap->data[heap->last]; (heap->last)--; (heap->size)--; ReheapDown(heap, 0); return 1; }

19 從堆積移除節點 從堆積 heap 裡移除資料 *dataptr 所指的節點，該指標為資料陣列第零個元素的位址，即 heap->data[0]，它是堆積裡最大值者，然後將最後的元素移到陣列第零個元素的位址，進行 ReheapDown() 再堆下作業，使滿足堆積的要求。ReheapDown() 再堆下函式屬於遞迴函式，一層一層往下堆積，直到最後一個元素那一層時才停止。最後將 last 及 size 成員值均減一。傳回 1 值。若 size 成員值已達 0 值則傳回 0 值。

20 8.7 測試程式 上面說明的堆積結構宣告以及相關的函式存入 heap.h 表頭檔備用。
下列的程式 heap.c 用於測試 heap.h 表頭檔的函式是否正確無誤。首先建立一個 heap 堆積，最大元素個數為 16，資料比較函式名稱為 compareInt。 struct heapTag *heap; heap = heapCreate(16,compareInt); 執行時從整數陣列 k[ ] 依序輸入下列的數字。

21 依序插入9,24,45,13,21時之堆積

22 依序插入53,15時之堆積

23 依序插入19時之堆積及陣列 根節點為第 0 個元素，其值為 53 最大，它的左子樹在第 1 個位置，其值為 21，它的右子樹在第 2 個位置，其值為 45。 節點 21 在第 1 個位置，左子樹在第 2*1+1=3 個位置，其值為 19，右子樹在第 2*1+2=4 個位置，其值為 13。 節點 45 在第 2 個位置，左子樹在第 2*2+1=5 個位置，其值為 24，右子樹在第 2*2+2=6 個位置，其值為 15。 節點 19 在第 3 個位置，左子樹在第 2*3+1=7 個位置，其值為 9，沒有右子樹。

24 8.8 優先佇列 許多出國旅遊的人在機場登機時，常看到機組員最先登機，然後持有貴賓卡的人登機，然後孕婦或帶嬰兒的人登機，最後才是一般乘客登機，很顯然因為身份的不同，處理的方式也不同，某些人要優先處理。 就以這四類的人員說明。設機組員的優先碼為 4，貴賓優先碼為 3，孕婦優先碼為 2，一般乘客優先碼為 1。登機時機組員佇列在最前面，然後為貴賓佇列，其後為孕婦佇列，最後才是一般乘客佇列。

25 優先佇列 我們使用電腦來模擬，若每一個人有一個識別碼，一般是護照號碼或身份證字號，還有一個優先碼，這四類的人有先來後到的，若輸入檔案的內容如下： 101 1 103 3 104 4 204 4 202 2 203 3 201 1 301 1 304 4 302 2 303 3 第一個欄位為識別碼，為了簡單起見識別碼採用三位數字，第二欄為優先碼，一位數字 1～4，優先碼 4 最優先。

26 優先佇列 現在我們要從中選出各類人員，各自獨立一個佇列如下： 機組員 貴賓 孕婦 一般乘客
機組員 貴賓 孕婦 一般乘客

27 優先佇列 第一個登機的給順號 999，第二個登機的給順號 998，逐次遞減，此順號配合優先碼，構成一個序號 serial，由「優先碼.順號」組成，因此輸入檔 priqueue.txt 讀入的資料經電腦編成序號如下： 序號 就以此序號當堆積資料比較的基礎。每一類別人員建立一個如下的資料結構custNodeTag。

28 優先佇列 就以此序號當堆積資料比較的基礎。每一類別人員建立一個如下的資料結構 custNodeTag。 struct custNodeTag
{ int id; int priority; int serial; }; 其中 id 成員為人員識別碼，priority 為優先碼，serial 為序號。所建立的堆積如下圖所示。

29 登機人員所建立的堆積

30 登機人員所建立的 heap 堆積 登機人員所建立的 heap 堆積，在根節點序號 4997 是堆積裡頭最大的，他的優先碼為 4，屬於最優先的一群。移除 4997 節點後，4996 次大值變成新的根節點，接著移除，第三大值的 4991 變成新的根節點，如此循序移除，直到沒有節點為止，移除的節點資料除了顯示在螢幕之外，還輸出至 priqueue.lst 本文檔。

31 登機人員所建立的 heap 堆積輸出如下 id priority serial 104 4 4997 204 4 4996

32 8.9 最小堆積 前面所處理的堆積為內定的最大堆積，若要建立最小堆積又如何？只要修改再堆上 ReheapUp() 及再堆下 ReheapDown() 這兩個函式就行，修改如下：

33 /*exchange*/ /*when child*/ /* < parent*/
void ReheapUp(struct heapTag *heap, int child) { int parent; void **data, *temp; if (child != 0) data = heap->data; parent = (child - 1)/ 2; if (heap->compare(data[child],data[parent])<0) temp=data[parent]; data[parent]=data[child]; data[child]=temp; ReheapUp (heap, parent); } return; /*exchange*/ /*when child*/ /* < parent*/

34 最小堆積 修改成子女節點之較小者，比父母節點小時，互換其值，小者往上升或往下降。
修改 heap.h 後的檔案改名為 minheap.h 表頭檔備用。 下列程式 minheap.c 用於測試 minheap.h 是否正確。執行時依序從整數 k[] 陣列取得下列資料建立 heap 最小堆積，輸入資料如下： 所建立的堆積如下圖所示。

35 最小堆積 執行時依序從整數 k[] 陣列取得下列資料建立 heap 最小堆積，輸入資料如下：