C語言實現小根堆：順序存儲、插入刪除算法與圖解演示

堆是完全二叉樹，適合順序存儲 (陣列)。本文實現小根堆 (最小堆)，含初始化、插入 (上浮)、刪除堆頂 (下沉)、堆排序演示，附帶詳細圖解過程。

順序存儲映射規則 (0-based 索引)

• 父節點 i → 左子 2i+1，右子 2i+2
• 子節點 i → 父節點 (i-1)/2
• 葉子節點索引範圍：[n/2, n-1]

核心操作

插入 (上浮)

1. 新元素放入陣列尾部 heap[len++]。
2. 當前索引 i = len-1，父索引 j = (i-1)/2。
3. 若 heap[i] < heap[j]，交換 (或移動父節點下沉)，i = j 繼續。
4. 直到 i==0 或 heap[i] >= heap[j]，放入最終位置。

刪除堆頂 (下沉)

1. 保存堆頂 heap[0]，尾元素 heap[--len] 移至頂部暫存 x。
2. 從 i=0 開始，左子 j=2i+1。
3. 若右子存在且更小，j++。
4. 若 x <= heap[j] 停止；否則 heap[i] = heap[j] (子節點上移)，i=j 繼續。
5. 將 x 放入最終位置，返回原堆頂值。

完整代碼 (heap.c)

#include 
#include 

typedef int ElemType;
typedef struct { ElemType *heap; int len, maxSize; } Heap;

void init(Heap *h, int ms) {
    h->heap = malloc(ms * sizeof(ElemType));
    h->len = 0; h->maxSize = ms;
}

void push(Heap *h, ElemType x) {
    if (h->len == h->maxSize) { /* realloc 2x */ }
    int i = h->len++;
    while (i > 0) {
        int p = (i-1)/2;
        if (x >= h->heap[p]) break;
        h->heap[i] = h->heap[p];
        i = p;
    }
    h->heap[i] = x;
}

ElemType pop(Heap *h) {
    ElemType top = h->heap[0];
    ElemType x = h->heap[--h->len];
    int i = 0, c = 1;
    while (c < h->len) {
        if (c+1 < h->len && h->heap[c+1] < h->heap[c]) c++;
        if (x <= h->heap[c]) break;
        h->heap[i] = h->heap[c];
        i = c; c = 2*i + 1;
    }
    h->heap[i] = x;
    return top;
}

int main() {
    Heap h; init(&h, 5);
    int a[] = {23,56,40,62,38,55,10,16};
    for (int i=0; i<8; ++i) push(&h, a[i]);
    while (h.len) printf("%d%c", pop(&h), h.len?',':'\n');
    free(h.heap);
    return 0;
}

運行結果

10,16,23,38,40,55,56,62

輸出有序序列，驗證堆性質正確。

圖解關鍵步驟

插入 16 過程 (上浮)

插入前:        10           插入 16 到尾部:        10
             /    \                    /    \
           23      38                23      38
          / \    / \                / \    / \
         40 55  56  62             40  55 56  62
                                      /
                                     16 (新節點)
上浮: 16 < 38 交換 → 16 < 10? 否 → 結束
最終:        10
             /    \
           16      23
          / \    / \
         40 55  56  62
        /
       38

刪除堆頂 10 過程 (下沉)

刪除前:        10           尾元素 62 移頂:        62
             /    \                    /    \
           16      23                16      23
          / \    / \                / \    / \
         38 40  55  56             38  40 55  56
下沉: 62 > 16 和 23，與較小者 16 交換 → 62 > 38 和 40，與 38 交換 → 葉子停止
最終:        16
             /    \
           38      23
          / \    / \
         62 40  55  56

複雜度與應用

• 插入/刪除：O(log n)，空間 O(n)。
• 堆排序：重複 pop 得有序序列，原地排序 O(n log n)。
• 應用：優先隊列、Top-K 問題、Dijkstra/Prim 算法、中位數維護。