資料結構核心：二叉堆 C 語言完整實現指南

編輯：關於C語言

前言

二叉堆是實現優先佇列最經典、最高效的資料結構之一。它基於完全二叉樹，以陣列為底層存儲，實現了 O(log N) 的插入與刪除最小值（或最大值）操作。本文詳細解析二叉堆的存儲映射、核心操作（上濾/下濾）、哨兵節點技巧，並提供生產級的 C 語言完整 ADT 實現。

一、存儲結構：完全二叉樹的陣列映射

完全二叉樹的關鍵性質：節點間的邏輯關係可直接用陣列下標算術表示，無需指釖。

方案 A：根節點下標為 0

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

方案 B：根節點下標為 1（推薦，配合哨兵）

左子女：2*i
右子女：2*i + 1
父節點：i/2

方案 B 的優勢：父節點計算僅需一條移位/除法指令，且 Elements[0] 可放置哨兵（極小值），簡化上濾循環邊界判斷。

ADT 定義

typedef int ElementType;

struct HeapStruct {
    int Capacity;       // 最大容量
    int Size;           // 當前元素數
    ElementType *Elements; // 陣列基址 (長度 Capacity+1，索引 0 為哨兵)
};
typedef struct HeapStruct *PriorityQueue;

二、核心操作詳解

1. 插入操作 —— 上濾

邏輯：新元素置於堆尾（Size+1），循環與父節點比較，若小於父節點則將父節點下移，直至找到合適位置或到達根節點（哨兵保證循環終止）。

void Insert(ElementType X, PriorityQueue H) {
    if (IsFull(H)) { Error("Priority queue is full"); return; }

    int i;
    for (i = ++H->Size; H->Elements[i/2] > X; i /= 2)
        H->Elements[i] = H->Elements[i/2]; // 父節點下移
    H->Elements[i] = X; // 找到位置，放入
}

時間複雜度：O(log N)（樹高）。哨兵作用：循環條件 H->Elements[i/2] > X 在 i=1 時比較 Elements[0] (哨兵極小值)，必然為假，自然退出，無需額外 i>1 判斷。

2. 刪除最小值操作 —— 下濾

邏輯：取走根節點（最小值），將堆尾最後一個元素移至根，然後循環與兩個子女中較小者比較，若大於該子女則將子女上移，直至找到位置或成為葉節點。

ElementType DeleteMin(PriorityQueue H) {
    if (IsEmpty(H)) { Error("Priority queue is empty"); return H->Elements[0]; }

    ElementType MinElement = H->Elements[1];
    ElementType LastElement = H->Elements[H->Size--]; // 取走最後元素，Size--

    int i, Child;
    for (i = 1; i*2 <= H->Size; i = Child) {
        Child = i*2; // 左子女
        // 找出較小的子女
        if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child])
            Child++;
        // 下濾判斷
        if (LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child]; // 子女上移
        else
            break; // 找到位置
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

關鍵細節：

Child != H->Size 判斷右子女是否存在（避免越界）。
循環條件 i*2 <= H->Size 確保當前節點至少有左子女（完全二叉樹性質）。
將 LastElement 暫存，避免多次陣列寫入，僅在最終位置寫入一次。

三、完整 ADT 實現

binheap.h (介面)

#ifndef BINHEAP_H_INCLUDED
#define BINHEAP_H_INCLUDED

typedef int ElementType;
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);

#endif

binheap.c (實現)

#include "binheap.h"
#include "fatal.h" // 假設提供 Error(), FatalError()
#include 

#define MinPQSize 10
#define MinData -32767 // 哨兵值，假設 ElementType 為 int 且業務數據 > MinData

struct HeapStruct {
    int Capacity;
    int Size;
    ElementType *Elements;
};

PriorityQueue Initialize(int MaxElements) {
    if (MaxElements < MinPQSize) Error("Priority queue size is too small");
    PriorityQueue H = malloc(sizeof(struct HeapStruct));
    if (!H) FatalError("Out of space!!!");
    H->Elements = malloc((MaxElements + 1) * sizeof(ElementType)); // +1 for sentinel
    if (!H->Elements) FatalError("Out of space!!!");
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData; // 哨兵
    return H;
}

void MakeEmpty(PriorityQueue H) { H->Size = 0; }

// Insert, DeleteMin 同前文

ElementType FindMin(PriorityQueue H) {
    if (!IsEmpty(H)) return H->Elements[1];
    Error("Priority Queue is Empty");
    return H->Elements[0];
}

int IsEmpty(PriorityQueue H) { return H->Size == 0; }
int IsFull(PriorityQueue H) { return H->Size == H->Capacity; }

void Destroy(PriorityQueue H) {
    free(H->Elements);
    free(H);
}

四、進階話題與擴展

建堆優化：若已有 N 個元素，可用 O(N) 的 BuildHeap（從最後一個非葉節點倒序下濾），優於 N 次 Insert 的 O(N log N)。
最大堆：比較邏輯反向（< 改 >），哨兵改為極大值。
泛型化：用 void* + 比較函數指標替換 ElementType，支援任意類型。
應用場景：Dijkstra/A* 最短路徑、Huffman 編碼、任務調度、Top-K 問題、計時器輪。