優先隊列在 C 語言中的實現：基於二叉堆的 KeyValue 結構與完整 API 設計

注意：原文為 C 語言實現，非 Java

本文對原文 C 代碼進行整理、註釋補充與架構說明，幫助理解基於二叉堆的優先隊列核心邏輯，供跨語言學習參考。

數據結構設計

// 鍵值對：key 為優先級，_value 指向業務數據
typedef struct key_value_struct KeyValue;
struct key_value_struct {
    int _key;
    void *_value;
};

// 優先隊列：動態數組實現二叉堆
#define PRIORITY_MAX 1  // 最大堆
#define PRIORITY_MIN 2  // 最小堆

typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct {
    KeyValue **_nodes;   // 堆數組
    int _size;           // 當前元素數
    int _capacity;       // 數組容量
    int _priority;       // PRIORITY_MAX / PRIORITY_MIN
};

核心 API

堆調整核心邏輯（以最大堆為例）

入隊：上浮

1. 新元素放入數組尾部 _nodes[_size++]。
2. 當前索引 i = _size - 1，父節點 parent = (i-1)/2。
3. 若 child.key > parent.key 則交換，i = parent 繼續上浮；否則停止。

出隊：下沉

1. 保存堆頂 _nodes[0] 作為返回值。
2. 將尾部元素 _nodes[_size-1] 移至堆頂，_size--。
3. 從根節點 i=0 開始，比較左右子節點 left=2i+1, right=2i+2。
4. 取較大子節點 j，若 parent.key < child.key 則交換，i=j 繼續下沉；否則停止。

動態擴容策略

static void priority_queue_realloc(PriorityQueue *pq) {
    pq->_capacity *= 2;
    pq->_nodes = realloc(pq->_nodes, sizeof(KeyValue*) * pq->_capacity);
}

入隊時若 _size >= _capacity 觸發 2 倍擴容，均攤 O(1)。

比較器統一抽象

static int priority_queue_compare(PriorityQueue *pq, int pos1, int pos2) {
    int r = pq->_nodes[pos1]->_key - pq->_nodes[pos2]->_key;
    if (pq->_priority == PRIORITY_MAX) r *= -1; // 最大堆取反
    return r;
}

同一比較邏輯服務於上浮/下沉，通過 _priority 切換大/小頂堆行為。

測試主程序

int main() {
    PriorityQueue *pq = priority_queue_new(PRIORITY_MAX);
    int data[] = {1, 9, 7, 8, 5, 4, 3, 2, 1, 100, 50, 17};
    for (int v : data) {
        KeyValue *kv = key_value_new(v, NULL);
        priority_queue_enqueue(pq, kv);
    }
    priority_queue_print(pq); // 打印堆內順序 + 依次出隊驗證
    priority_queue_free(pq, NULL);
    return 0;
}

Java 對應實現參考

Java 中直接使用 java.util.PriorityQueue<E>：

// 最大堆（預設最小堆，需反轉比較器）
PriorityQueue maxHeap = new PriorityQueue<>((a,b) -> b - a);
maxHeap.offer(100); maxHeap.offer(50);
System.out.println(maxHeap.poll()); // 100

// 自定義對象
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));

💡 對比：C 需手動管理記憶體、指針、擴容、比較器；Java 集合框架已封裝完備，開箱即用，專注業務邏輯。