優先佇列

永遠先拿最大的那個。 · ⏱ 約 30 分鐘

你會學到三件事

1. priority_queue 每次拿出來的都是最大的
2. 它是 O(log n) 進、O(log n) 出、O(1) 看
3. 貪心：每一步都選當下最好的

開始之前

上一課的兩個容器，順序是「什麼時候進來」決定的。

這一課的容器，順序是值本身決定的。

一、每次拿最大的

priority_queue<int> pq;
pq.push(3);
pq.push(7);
pq.push(1);
cout << pq.top() << endl;      // 7   ← 最大的
pq.pop();
cout << pq.top() << endl;      // 3   ← 剩下裡面最大的

⚠️ 和 stack 一樣用 top()，而意思完全不同： stack 的 top 是「最後放的」，這裡是「最大的」。

二、要最小的

priority_queue<int, vector<int>, greater<int>> pq;

⚠️ 這個寫法很長而且要背——中間那個 vector<int> 不能省， 即使你根本不關心它。

（那是因為第三個參數是比較器，而 C++ 要求前面的都給。）

小的先出 在 Dijkstra（第 12 課）裡是必須的。

三、為什麼不是「排好序的 vector」

差別在一直有新東西進來的時候。

它裡面是一個叫 heap 的結構——一棵「父親一定比兒子大」的樹。 它不是完全排好序的，而「最大的在最上面」永遠成立。

只需要最大的話，不必把全部排好。 這就是它比排序快的原因。

⚠️ 所以 priority_queue 不能走訪——沒有 begin()， 因為裡面根本不是有序的。

四、貪心：每一步選當下最好的

貪心 = 每一步都選當下看起來最好的，不回頭。

它很快，而它不一定對。

題目：用最少的硬幣湊出 15 元，幣值 {1, 5, 10}
貪心：10 + 5 = 兩枚         ✅ 對

同一個做法，幣值 {1, 7, 10}，湊 14
貪心：10 + 1 + 1 + 1 + 1 = 五枚
最佳：7 + 7 = 兩枚           🔴 貪心錯了

⚠️ 所以用貪心之前要能說出「為什麼這樣選一定對」。 說不出來就用動態規劃（第 10 課）。

而 priority_queue 正是貪心的標準工具——「當下最好的」就是 top()。

完成的樣子

int main() {
    priority_queue<int> pq;
    pq.push(3);
    pq.push(7);
    pq.push(1);
    cout << pq.top() << endl;
    pq.pop();
    cout << pq.top() << endl;
    return 0;
}

換你了

合併果子：有 n 堆果子，每次合併兩堆的成本是它們的重量和， 求把全部合成一堆的最小總成本。

提示：每次合併最小的兩堆——用小的先出的那種 priority_queue。

⚠️ 而做完之後想一下：為什麼「每次選最小的兩堆」一定是對的？

這一課你做了什麼

• 你用 priority_queue 做出了「永遠先拿最大」的容器
• 你知道它比排序快，因為它不需要全部有序
• 你知道貪心很快，而它需要一個「為什麼對」的理由

如果卡住了