最小堆 / 優先隊列

堆是經過排序的完全二叉樹。最小堆：根節點鍵值最小。優先隊列可用堆實現，最高優先級元素先出（largest-in, first-out）。本文提供完整 C 實現。

數據結構定義

/* MinHeap.h */
#ifndef MIN_HEAP_H
#define MIN_HEAP_H

typedef struct MinHeap *MinPriorityQueue;
typedef int ElementType;

MinPriorityQueue initialize(int maxElements);
void destroy(MinPriorityQueue pq);
void makeEmpty(MinPriorityQueue pq);
void insert(ElementType x, MinPriorityQueue pq);
ElementType deleteMin(MinPriorityQueue pq);
ElementType findMin(MinPriorityQueue pq);
int isEmpty(MinPriorityQueue pq);
int isFull(MinPriorityQueue pq);
MinPriorityQueue buildHeap_insert(int *arr, int n);
MinPriorityQueue buildHeap_percolate(int *arr, int n);
void printMinPriorityQueue(MinPriorityQueue pq);

#endif

核心實現

/* MinHeap.c */
#include 
#include 
#include "MinHeap.h"

#define SentinelElement -1  // 哨兵，小於所有元素

struct MinHeap {
    int capacity;
    int size;
    ElementType *elements;  // elements[0] 為哨兵
};

MinPriorityQueue initialize(int maxElements) {
    if (maxElements <= 0) return NULL;
    MinPriorityQueue pq = malloc(sizeof(struct MinHeap));
    pq->capacity = maxElements;
    pq->size = 0;
    pq->elements = malloc(sizeof(ElementType) * (maxElements + 1));
    pq->elements[0] = SentinelElement;
    return pq;
}

void insert(ElementType x, MinPriorityQueue pq) {
    if (isFull(pq)) return;
    int i;
    for (i = ++pq->size; x < pq->elements[i/2]; i /= 2)
        pq->elements[i] = pq->elements[i/2];  // 下濾
    pq->elements[i] = x;
}

ElementType deleteMin(MinPriorityQueue pq) {
    if (isEmpty(pq)) return SentinelElement;
    ElementType min = pq->elements[1];
    ElementType last = pq->elements[pq->size--];
    int i, child;
    for (i = 1; i*2 <= pq->size; i = child) {
        child = i*2;
        if (child < pq->size && pq->elements[child] > pq->elements[child+1])
            child++;  // 取較小子節點
        if (last < pq->elements[child]) break;
        pq->elements[i] = pq->elements[child];  // 上濾
    }
    pq->elements[i] = last;
    return min;
}

/* Floyd 建堆法：O(N) */
void percolateDown(int *arr, int len, int i) {
    int n = len - 1, tmp;
    if (i*2 == n && arr[i] > arr[n]) { tmp=arr[i]; arr[i]=arr[n]; arr[n]=tmp; }
    else if (i*2 < n) {
        int smaller = (arr[i*2] < arr[i*2+1]) ? i*2 : i*2+1;
        if (arr[i] > arr[smaller]) { tmp=arr[i]; arr[i]=arr[smaller]; arr[smaller]=tmp; }
    }
}
MinPriorityQueue buildHeap_percolate(int *arr, int n) {
    MinPriorityQueue pq = malloc(sizeof(struct MinHeap));
    pq->elements = malloc(sizeof(ElementType)*(n+1));
    pq->elements[0] = SentinelElement;
    for (int i=1;i<=n;i++) pq->elements[i]=arr[i-1];
    for (int i=n/2;i>0;i--) percolateDown(pq->elements, n+1, i);
    pq->size = n; pq->capacity = n*2;
    return pq;
}

測試驗證

int main() {
    int a[5] = {5,4,3,2,1};
    MinPriorityQueue pq1 = buildHeap_insert(a,5);
    MinPriorityQueue pq2 = buildHeap_percolate(a,5);
    printMinPriorityQueue(pq1);
    printMinPriorityQueue(pq2);
    return 0;
}
/* 輸出：
插入法：1 2 4 5 3
下濾法：1 5 3 2 4
兩者皆滿足最小堆性質，結構不同但均正確 */

複雜度分析

最大堆實現

只需將比較方向反轉（x > pq->elements[i/2]），其餘邏輯完全相同。