優先隊列：數據結構原理與 C++ STL 實戰

優先隊列是特殊的隊列，元素按優先級出隊而非先進先出。它是堆（Heap）的經典應用，廣泛用於任務調度、最短路徑、數據流處理等場景。

核心特性

• 頂部元素：始終為最高（或最低）優先級
• 插入：O(log n) — 堆化上浮
• 刪除頂部：O(log n) — 堆化下沉
• 查看頂部：O(1)

底層實現：二叉堆

完全二叉樹 + 數組存儲：

• 父節點索引 i → 左子節點 2i+1，右子節點 2i+2
• 子節點索引 j → 父節點 (j-1)/2
• 大頂堆：arr[parent] >= arr[child]

C++ STL priority_queue

#include <queue>
#include <vector>
#include <functional>  // std::greater

// 默認大頂堆（最大元素優先）
std::priority_queue max_heap;

// 小頂堆（最小元素優先）
std::priority_queue, std::greater> min_heap;

// 自定義比較（如結構體）
struct Task {
    int id, priority;
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 大頂堆
    }
};
std::priority_queue task_queue;

常用操作

經典應用場景

1. 任務調度系統

// 高優先級任務優先執行
priority_queue scheduler;
scheduler.push({1, 10});  // 緊急任務
scheduler.push({2, 5});   // 普通任務
while (!scheduler.empty()) {
    execute(scheduler.top());
    scheduler.pop();
}

2. Dijkstra 最短路徑

// 優先隊列優化：O((V+E)log V)
priority_queue, vector>, greater>> pq;
pq.push({0, start});  // {距離, 頂點}
while (!pq.empty()) {
    auto [dist, u] = pq.top(); pq.pop();
    if (dist > d[u]) continue;  // 延遲刪除
    for (auto [v, w] : adj[u]) {
        if (d[v] > d[u] + w) {
            d[v] = d[u] + w;
            pq.push({d[v], v});
        }
    }
}

3. 數據流中位數 / Top-K

// 維護兩個堆：大頂堆存較小半，小頂堆存較大半
priority_queue max_heap;  // 左半部
priority_queue, greater> min_heap;  // 右半部

void addNum(int num) {
    max_heap.push(num);
    min_heap.push(max_heap.top()); max_heap.pop();
    if (max_heap.size() < min_heap.size()) {
        max_heap.push(min_heap.top()); min_heap.pop();
    }
}
double findMedian() {
    if (max_heap.size() > min_heap.size()) return max_heap.top();
    return (max_heap.top() + min_heap.top()) / 2.0;
}

手寫實現要點（面試常考）

template>
class PriorityQueue {
    std::vector heap;
    Compare comp;
    
    void sift_up(int i) {
        while (i > 0 && comp(heap[(i-1)/2], heap[i])) {
            std::swap(heap[(i-1)/2], heap[i]);
            i = (i-1)/2;
        }
    }
    
    void sift_down(int i) {
        int n = heap.size();
        while (2*i+1 < n) {
            int child = 2*i+1;
            if (child+1 < n && comp(heap[child], heap[child+1])) child++;
            if (!comp(heap[i], heap[child])) break;
            std::swap(heap[i], heap[child]);
            i = child;
        }
    }
public:
    void push(const T& val) { heap.push_back(val); sift_up(heap.size()-1); }
    void pop() { heap[0] = heap.back(); heap.pop_back(); sift_down(0); }
    const T& top() const { return heap[0]; }
    bool empty() const { return heap.empty(); }
};

性能對比與選型建議

優先隊列將「動態維護極值」這一核心需求封裝為優雅接口，是算法工程師工具箱中的利器。熟練掌握其原理與 STL 用法，能顯著提升解決複雜問題的效率。