昨天的選擇排序每一輪都要把剩下的資料從頭看到尾，才找得出最小值，要做 n − 1 輪，總共 O(n²)，問題出在「找最值」太慢。

累堆（heap）正好擅長這件事：最大累堆的樹根就是最大值，取走後沿著一條路徑往下調整，就能讓下一個最大值回到樹根，每次只要 O(log n)。用累堆來找最值的排序方法，就是累堆排序（heap sort）。

以下 n 代表資料筆數，範例沿用前面介紹排序方法時的同一組 8 筆資料：

26  59  1  61  5  15  11  37

先複習：最大累堆

最大累堆（max heap）的形狀是完整二元樹（除了最底層都填滿，最底層從左到右連續排列），而且每個父節點都不小於子節點，所以最大值在樹根。

完整二元樹可以直接存在陣列裡。索引從 1 開始存放時（索引 0 不用），索引 i 的左子節點在 2i、右子節點在 2i + 1。

累堆排序會反覆用到往下調整：節點比子節點小時，就和較大的子節點交換，一路往下換，直到不比子節點小或沒有子節點為止。和較大的交換，換上去的才不會比另一個子節點小。

第一階段：把陣列建成最大累堆

8 筆資料依序放進索引 1～8，形狀已經是完整二元樹，只是還不符合父子大小的規定：

做法是從最後一個有子節點的節點（索引 n / 2）開始，往前到樹根，逐一往下調整。範例從索引 4 做到索引 1（圖中左邊的橘色節點）；葉節點本身就符合規定，不用處理。

要從後往前，是因為往下調整一個節點時，它的兩棵子樹必須已經是最大累堆；從後往前做，輪到某個節點時，底下的節點都已經處理好了。

第二階段：一個一個取出最大值

1. 樹根（最大值）和累堆的最後一個節點交換，最大值就到了它的最終位置。
2. 累堆大小減 1，剛換到尾端的最大值不再屬於累堆。
3. 新的樹根通常太小，對它往下調整。
4. 重複步驟 1～3，直到累堆只剩 1 個節點。

以圖中第一次取出為例：61 和 26 交換後，26 小於較大的子節點 59，兩者交換；換到索引 2 後，又小於較大的子節點 37，再交換一次。這時 26 在索引 4，它的子節點索引 8 放的是已排好的 61，不屬於累堆，所以調整停止，59 成為新的樹根。

每次都把目前最大的資料換到最後面，排好的部分從陣列尾端往前長出來。由小到大排序用最大累堆；要由大到小，就改用最小累堆。

用 C 語言實作

程式中的 heap[0] 不使用，資料放在 heap[1]～heap[n]：

#include <stdio.h>

#define SIZE 8

void printHeap(const int heap[], int first, int last) {
    for (int i = first; i <= last; i++) {
        printf("%d ", heap[i]);
    }
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* 往下調整：索引 i 的節點和較大的子節點比較，比它小就交換，直到放對位置 */
void siftDown(int heap[], int i, int heapSize) {
    while (2 * i <= heapSize) {
        int child = 2 * i; /* 左子節點 */
        if (child + 1 <= heapSize && heap[child + 1] > heap[child]) {
            child++; /* 右子節點比較大，改和右邊比 */
        }
        if (heap[i] >= heap[child]) {
            break;
        }
        swap(&heap[i], &heap[child]);
        i = child;
    }
}

/* heap[1..n] 存放資料，heap[0] 不使用 */
void heapSort(int heap[], int n) {
    /* 第一階段：從最後一個有子節點的節點開始，往前逐一往下調整，建成最大累堆 */
    for (int i = n / 2; i >= 1; i--) {
        siftDown(heap, i, n);
    }
    printf("建好的最大累堆：");
    printHeap(heap, 1, n);
    printf("\n");

    /* 第二階段：樹根（最大值）和最後一個節點交換，累堆縮小 1，再往下調整 */
    for (int last = n; last >= 2; last--) {
        swap(&heap[1], &heap[last]);
        siftDown(heap, 1, last - 1);
        printf("取出 %2d：", heap[last]);
        printHeap(heap, 1, last - 1);
        printf("| ");
        printHeap(heap, last, n);
        printf("\n");
    }
}

int main(void) {
    int heap[SIZE + 1] = {0, 26, 59, 1, 61, 5, 15, 11, 37};

    heapSort(heap, SIZE);

    printf("排序結果：");
    printHeap(heap, 1, SIZE);
    printf("\n");
    return 0;
}

執行結果，| 右邊是已經排好的部分：

建好的最大累堆：61 59 15 37 5 1 11 26
取出 61：59 37 15 26 5 1 11 | 61
取出 59：37 26 15 11 5 1 | 59 61
取出 37：26 11 15 1 5 | 37 59 61
取出 26：15 11 5 1 | 26 37 59 61
取出 15：11 1 5 | 15 26 37 59 61
取出 11：5 1 | 11 15 26 37 59 61
取出  5：1 | 5 11 15 26 37 59 61
排序結果：1 5 11 15 26 37 59 61

siftDown 的 heapSize 表示目前累堆的範圍。已經換到尾端的資料雖然還在同一個陣列裡，但超出 heapSize，往下調整時不會碰到它們。

時間、空間與穩定性

時間上限 O(n log n)。 第二階段取出 n − 1 次，每次往下調整最多走樹高約 log₂ n 步。第一階段雖然要調整 n / 2 個節點，但大部分節點在下層，能往下走的步數很少（約一半是葉節點，完全不用動），加總後只要 O(n)。所以累堆排序不會因為資料順序而退化成 O(n²)。

往下調整也可能提早停止：如果所有值都相同，每次一比較就停，總時間只有 O(n)。因此允許重複值時，最好情況是 O(n)；鍵值互不相同時，最好情況仍是 n log n 等級。

額外空間 O(1)。 所有交換都在原陣列中進行，是原地排序；陣列版的合併排序則需要 O(n) 的暫存陣列。

累堆排序不穩定。 樹根和最後一個節點交換時，資料會被遠距離搬動。例如「紅 5、黑 5、9」：建堆後變成「9、黑 5、紅 5」；取出 9 後是「紅 5、黑 5 | 9」；再取出紅 5，和黑 5 交換，結果是「黑 5、紅 5、9」，兩張 5 的順序顛倒了。

和其他排序方法比較

表中累堆排序允許重複值；鍵值互異時，最好情況改為 O(n log n)。快速排序的平均表現則假設鍵值互異、排列隨機。

• 和選擇排序比：一樣每輪挑出最值放到定位，但累堆只要 O(log n) 就能找到下一個最值，可以看成選擇排序的改良版。
• 和快速排序比：最壞也不會退化；但累堆在陣列中的存取位置跳來跳去（i 和 2i 隔得越來越遠），實際速度通常不如快速排序。
• 和合併排序比：兩者都保證 O(n log n)；累堆排序只要 O(1) 額外空間，合併排序則是穩定的。

小結

累堆排序先用 O(n) 建成最大累堆，再反覆把樹根換到尾端，讓排好的部分從後往前增加。時間不超過 O(n log n)，只需要 O(1) 額外空間，但不穩定。

今日重點：

• 累堆排序：先建成最大累堆，再反覆把樹根換到尾端、縮小累堆、往下調整。
• 往下調整要和較大的子節點交換，直到不比子節點小，或沒有子節點。
• 建堆從索引 n / 2 往前做到索引 1，時間 O(n)；取出 n − 1 次，每次最多 O(log n)。
• 時間上限 O(n log n)，允許重複值時最好可達 O(n)；額外空間 O(1)，不穩定。

到這裡，排序方法看起來不是 O(n²) 就是 O(n log n)。下一篇先替插入排序裝上「大步跳躍」的希爾排序，再認識一種完全不比大小、只看位數分桶子的基數排序，最後把所有排序方法排在一起比一比，看看遇到不同的資料該怎麼選。