堆排序完整實現指南：大頂堆構建、原地排序、優先隊列應用與工程優化

前言

堆排序是原地、不穩定、最壞 O(n log n) 保證 的選擇排序進化版。本文從完全二叉樹性質映射、大頂堆構建 (自下而上 Floyd 算法 vs 自上而下)、堆頂替換下沉、工程級優化 (底層葉子優化、分支預測友好)、優先隊列應用模式、測試驗證矩陣**提供 C 語言生產級實現。

一、堆的數組表示與性質

對 0 基數組 arr[0..n-1]：

• 父節點：(i - 1) / 2
• 左子節點：2*i + 1
• 右子節點：2*i + 2

大頂堆性質：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] (對所有非葉節點)。堆頂 arr[0] 為全局最大值。

二、堆構建：Floyd 算法 O(n) — 從最後非葉節點逆序下沉

核心洞察：葉節點天然滿足堆性質。從索引 (n-2)/2 (最後非葉節點) 遞減至 0，對每個節點執行 sift_down。數學證明總操作數 ≤ 2n。

static void sift_down(int arr[], int n, int i) {
    int max_idx = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[max_idx]) max_idx = left;
    if (right < n && arr[right] > arr[max_idx]) max_idx = right;
    
    if (max_idx != i) {
        int tmp = arr[i]; arr[i] = arr[max_idx]; arr[max_idx] = tmp;
        sift_down(arr, n, max_idx); // 遞歸下沉 (尾遞歸可展開為循環)
    }
}

static void build_max_heap(int arr[], int n) {
    for (int i = (n - 2) / 2; i >= 0; i--) {
        sift_down(arr, n, i);
    }
}

三、排序主流程：堆頂換尾 + 縮小堆範圍 + 下沉

void heap_sort(int arr[], int n) {
    if (!arr || n <= 1) return;
    
    // 1. 構建大頂堆
    build_max_heap(arr, n);
    
    // 2. 重複提取最大值
    for (int end = n - 1; end > 0; end--) {
        // 堆頂 (最大) 與當前末尾交換
        int tmp = arr[0]; arr[0] = arr[end]; arr[end] = tmp;
        // 在縮小的堆 [0..end-1] 上下沉新堆頂
        sift_down(arr, end, 0);
    }
}

四、工程優化：循環下沉 + 葉子節點快速路徑

遞歸 sift_down 有函數調用開銷。展開為循環，並優化「單子節點」情況 (僅左子節點存在)。

static void sift_down_opt(int arr[], int n, int i) {
    while (1) {
        int left = 2 * i + 1;
        if (left >= n) break; // 葉節點
        
        int right = left + 1;
        int max_idx = i;
        
        if (arr[left] > arr[max_idx]) max_idx = left;
        // 單子節點 (無右子) 直接比較左子
        if (right < n) {
            if (arr[right] > arr[max_idx]) max_idx = right;
        }
        
        if (max_idx == i) break; // 已滿足堆性質
        
        int tmp = arr[i]; arr[i] = arr[max_idx]; arr[max_idx] = tmp;
        i = max_idx; // 繼續下沉
    }
}

五、優先隊列應用模式 — 堆的動態接口

堆排序靜態構建一次；優先隊列需支持動態 push/pop/top。

// 上浮 (sift_up) 用於 push
static void sift_up(int arr[], int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (arr[i] <= arr[parent]) break;
        int tmp = arr[i]; arr[i] = arr[parent]; arr[parent] = tmp;
        i = parent;
    }
}

// 接口
void pq_push(int *arr, int *size, int capacity, int val) {
    if (*size >= capacity) return; // 或擴容
    arr[*size] = val;
    sift_up(arr, (*size)++);
}

int pq_pop(int *arr, int *size) {
    if (*size == 0) return INT_MIN;
    int top = arr[0];
    arr[0] = arr[--(*size)];
    sift_down_opt(arr, *size, 0);
    return top;
}

六、測試驗證矩陣

七、堆排序 vs 快速排序 vs 歸併排序：三國演義

結語

堆排序以「完全二叉樹隱式映射 + Floyd 線性構建 + 原地提取最大」的硬核邏輯，實現了最壯 O(n log n) + O(1) 空間的理論雙重保證。雖常數因子略大於快排，但在實時系統、內存極受限環境、動態優先隊列**場景不可替代。掌握 sift_down 循環優化與 sift_up 動態上浮，是從「會寫堆排」進階到「會用堆解決問題」的關鍵。