C 語言最大堆排序完整實作：建堆、調整、排序核心邏輯

堆排序核心概念

• 最大堆：父節點 ≥ 子節點，根節點為最大值
• 陣列表示：索引 0 為根，左子 2*i+1，右子 2*i+2，父 (i-1)/2
• 兩階段：建堆 (O(n)) + 重複提取最大值並調整 (O(n log n))

完整程式碼實作

#include 
using namespace std;

// 索引運算 (0-based)
inline int left(int i) { return 2*i + 1; }
inline int right(int i) { return 2*i + 2; }
inline int parent(int i) { return (i-1)/2; }

// 向下調整：維持以 i 為根的子樹為最大堆
void maxHeapify(int *arr, int n, int i) {
    if (!arr || i < 0) return;
    
    int l = left(i);
    int r = right(i);
    int largest = i;
    
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        maxHeapify(arr, n, largest); // 遞迴調整受影響子樹
    }
}

// 建堆：從最後一個非葉節點向前調整
void buildMaxHeap(int *arr, int n) {
    if (!arr || n <= 0) return;
    for (int i = n/2 - 1; i >= 0; i--) {
        maxHeapify(arr, n, i);
    }
}

// 堆排序主流程
void maxHeapSort(int *arr, int n) {
    if (!arr || n <= 0) return;
    
    buildMaxHeap(arr, n); // 階段 1：建立最大堆
    
    // 階段 2：重複提取最大值
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);       // 根 (最大) 換到末尾
        maxHeapify(arr, i, 0);      // 縮小堆範圍，調整新根
    }
}

int main() {
    int arr[] = {2, 3, 5, 1, 8, 6, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    maxHeapSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[i]); // 輸出: 1 2 3 4 5 6 8
    }
    return 0;
}

關鍵步驟圖解

初始陣列: [2, 3, 5, 1, 8, 6, 4]
建堆後:   [8, 3, 6, 1, 2, 5, 4]  (根為最大值 8)

排序過程:
i=6: swap(8,4) → [4,3,6,1,2,5,8] → heapify(6) → [6,3,5,1,2,4,8]
i=5: swap(6,4) → [4,3,5,1,2,6,8] → heapify(5) → [5,3,4,1,2,6,8]
i=4: swap(5,2) → [2,3,4,1,5,6,8] → heapify(4) → [4,3,2,1,5,6,8]
i=3: swap(4,1) → [1,3,2,4,5,6,8] → heapify(3) → [3,1,2,4,5,6,8]
i=2: swap(3,2) → [2,1,3,4,5,6,8] → heapify(2) → [2,1,3,4,5,6,8]
i=1: swap(2,1) → [1,2,3,4,5,6,8] → 完成

最終結果: [1, 2, 3, 4, 5, 6, 8]

複雜度分析

關鍵細節與優化

1. 0-based vs 1-based 索引：本文採 0-based (C/C++ 慣例)，左子 2i+1，右子 2i+2，父 (i-1)/2
2. 遞迴 vs 迭代：maxHeapify 遞迴深度 ≤ log n，棧溢位風險極低；可改寫為迭代略微提升效能
3. swap 宏 vs 函數：C++ 用 std::swap，C 可用宏或內聯函數
4. 穩定性：堆排序不穩定 (相等元素相對順序可能改變)

常見變體

• 最小堆排序：比較方向反轉，得到降序序列
• Top-K 問題：建大小為 K 的最小堆，掃描陣列維持堆內為前 K 大，O(n log K)
• 外部排序：結合歸併排序處理超大數據

結語

最大堆排序以原地排序、確定性 O(n log n)、無遞迴棧溢位風險 (非遞迴版) 成為嵌入式系統、即時系統的首選排序演算法。精通建堆線性時間證明、向下調整邏輯、索引運算三大核心，即能靈活應用於 Top-K、優先佇列、中位數維護等進階場景。