優先佇列

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

你會學到三件事

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

開始之前

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

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

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、每次拿最大的

不管放進去的順序，拿出來的永遠是最大的：

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

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

🟢 而積木上分得很清楚：這一顆寫著「… 的最大元素」， 上一課那顆寫著「… 的頂端元素」——同一個 top()，兩個名字。

二、要最小的

要反過來，宣告的時候多寫兩個參數：

1priority_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()。

完成的樣子

1#include <iostream>2#include <queue>3using namespace std;4int main() {5    priority_queue<int> pq;6    pq.push(3);7    pq.push(7);8    pq.push(1);9    cout << pq.top() << endl;10    pq.pop();11    cout << pq.top() << endl;12    return 0;13}

換你了

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

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

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

到編輯器做這一題：練習：合併果子的最小總成本

做一個

一串數字 5 1 9 3 7，印出最大的三個加起來是多少。

🔴 用 priority_queue：拿三次就好，不用排序整串。 ⚠️ 想一下：n 很大而 k 很小的時候，這個做法跟「排序完取前 k 個」差在哪裡？

到編輯器做這一題：做一個：前三大的和

這一課你做了什麼

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

如果卡住了