C語言實現通用堆（優先隊列）：從結構定義到核心操作完整指南

編輯：關於C語言

C語言實現通用堆（優先隊列）：從結構定義到核心操作完整指南

C++ 有 std::priority_queue，C 語言需自行構建。本文提供一個生產級的通用堆實現：支援自定義比較函數（小根/大根切換）、動態擴容、完整的插入/刪除/取頂操作，代碼結構清晰，可直接嵌入嵌入式或系統級專案。

核心資料結構

typedef int HeapElem;  // 元素類型，可改為 void* 實現完全泛型

typedef struct {
    int size;           // 當前元素數
    int capacity;       // 容量（以元素為單位）
    HeapElem* elems;    // 動態陣列
    int (*cmp)(const HeapElem*, const HeapElem*);  // 比較函數：<0 小於, =0 等於, >0 大於
} Heap;

比較函數範例

// 整數小根堆比較器
int cmpIntMin(const HeapElem* a, const HeapElem* b) {
    if (*a < *b) return -1;
    if (*a > *b) return 1;
    return 0;
}

// 整數大根堆比較器
int cmpIntMax(const HeapElem* a, const HeapElem* b) {
    return cmpIntMin(b, a);  // 交換參數即可反轉
}

核心操作實現

初始化與銷毀

int heapInit(Heap* h, int capacity, int (*cmp)(const HeapElem*, const HeapElem*)) {
    h->size = 0;
    h->capacity = capacity;
    h->elems = (HeapElem*)malloc(capacity * sizeof(HeapElem));
    h->cmp = cmp;
    return h->elems ? 0 : -1;
}

void heapDestroy(Heap* h) {
    free(h->elems);
    h->elems = NULL;
    h->size = h->capacity = 0;
    h->cmp = NULL;
}

上浮（Sift Up）——插入後恢復堆序

static void siftUp(Heap* h, int idx) {
    HeapElem tmp = h->elems[idx];
    while (idx > 0) {
        int parent = (idx - 1) >> 1;
        if (h->cmp(&h->elems[parent], &tmp) <= 0) break;
        h->elems[idx] = h->elems[parent];
        idx = parent;
    }
    h->elems[idx] = tmp;
}

下沉（Sift Down）——刪除頂端後恢復堆序

static void siftDown(Heap* h, int idx) {
    HeapElem tmp = h->elems[idx];
    int child;
    while ((child = (idx << 1) + 1) < h->size) {
        // 選擇較小的子節點（小根堆）
        if (child + 1 < h->size && h->cmp(&h->elems[child], &h->elems[child+1]) > 0)
            ++child;
        if (h->cmp(&tmp, &h->elems[child]) <= 0) break;
        h->elems[idx] = h->elems[child];
        idx = child;
    }
    h->elems[idx] = tmp;
}

公開介面

void heapPush(Heap* h, HeapElem x) {
    if (h->size == h->capacity) {
        int newCap = h->capacity * 2;
        HeapElem* tmp = (HeapElem*)realloc(h->elems, newCap * sizeof(HeapElem));
        if (!tmp) return;  // 或自定義錯誤處理
        h->elems = tmp;
        h->capacity = newCap;
    }
    h->elems[h->size++] = x;
    siftUp(h, h->size - 1);
}

void heapPop(Heap* h) {
    if (h->size == 0) return;
    h->elems[0] = h->elems[--h->size];
    siftDown(h, 0);
}

HeapElem heapTop(const Heap* h) {
    return h->elems[0];  // 調用者需自行確保 !heapEmpty(h)
}

bool heapEmpty(const Heap* h) { return h->size == 0; }
int heapSize(const Heap* h) { return h->size; }

使用範例：合併 K 個有序陣列

struct Node { int val; int arrIdx; int elemIdx; };

int cmpNode(const HeapElem* a, const HeapElem* b) {
    return ((Node*)a)->val - ((Node*)b)->val;
}

void mergeKArrays(int** arrays, int k, int* lens, int* out) {
    Heap h; heapInit(&h, k, cmpNode);
    for (int i = 0; i < k; ++i)
        if (lens[i] > 0)
            heapPush(&h, (HeapElem){arrays[i][0], i, 0});
    
    int idx = 0;
    while (!heapEmpty(&h)) {
        Node cur = *(Node*)heapTop(&h);
        heapPop(&h);
        out[idx++] = cur.val;
        if (cur.elemIdx + 1 < lens[cur.arrIdx])
            heapPush(&h, (HeapElem){arrays[cur.arrIdx][cur.elemIdx+1], cur.arrIdx, cur.elemIdx+1});
    }
    heapDestroy(&h);
}