🏆 C++ 的神奇“优先队列”（priority_queue）

——会自己排队的“超级队列”！

在 C++ 里，有一种非常聪明的“队列”，叫 priority_queue，中文意思是“优先队列”。
它的特别之处在于：
👉 不是谁先来谁先走，而是谁最重要，谁先走！

🎈先想象一个场景

假设在游乐园里，大家都在排队玩过山车。
普通的队列是这样的：

谁先排队，谁先玩。

而优先队列就不一样了，它会说：

谁的“优先级”高，谁就可以插到最前面！

比如：

• VIP 客人先上车

• 小宝宝优先

• 或者分数高的选手先领奖

它自己会帮忙“排好顺序”，让最高优先的人排在最前面。

🧱 在 C++ 里怎么写？

C++ 已经帮大家造好了这个“聪明的队列”，名字叫：

#include <queue>std::priority_queue<int> q;

这时候，q 就是一个“优先队列”啦。

往里面放数字（就像放人进队）：

q.push(3);
q.push(1);
q.push(5);

然后看队伍最前面的是谁：

std::cout << q.top(); // 输出：5

因为它会自动让最大的数字排在最前面。
这叫做一个“最大堆”（max-heap）。

🧮 它有哪些常见动作？

简单来说：

push 往里放，
pop 拿出去，
top 偷瞄一眼最前面的那个！

💡 想让“最小的”排最前？用这个！

默认情况下，priority_queue 会让最大的数排在前面。
如果希望最小的数排前面，只需要改成：

#include <queue>
#include <vector>
#include <functional>

std::priority_queue<int, std::vector<int>, std::greater<int>> q;

这时候：

q.push(5);
q.push(2);
q.push(9);
std::cout << q.top(); // 输出 2

变成了“最小堆”（min-heap）——越小越靠前。

🚗 举个生活中的例子：比赛颁奖

假设有一场比赛，有很多人得分，想要找出前 3 名：

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> scores = {88, 95, 60, 100, 72, 93};
    priority_queue<int, vector<int>, greater<int>> top3;

    for (int s : scores) {
        top3.push(s);
        if (top3.size() > 3)
            top3.pop(); // 保留分数最高的 3 个
    }

    cout << "前三名分数：";
    while (!top3.empty()) {
        cout << top3.top() << " ";
        top3.pop();
    }
}

C++98 兼容版本

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
    // 手动初始化 vector（不能用 {}）
    int arr[] = {88, 95, 60, 100, 72, 93};
    vector<int> scores(arr, arr + 6);

    // 注意模板参数间必须加空格 > >
    priority_queue<int, vector<int>, greater<int> > top3;

    // 不能用 range-based for，改为普通循环
    for (size_t i = 0; i < scores.size(); ++i) {
        top3.push(scores[i]);
        if (top3.size() > 3)
            top3.pop(); // 保留分数最高的3个
    }

    cout << "前三名分数：";
    while (!top3.empty()) {
        cout << top3.top() << " ";
        top3.pop();
    }
    cout << endl;

    return 0;
}

运行结果：

前三名分数：93 95 100

这个小程序自动帮忙找到前三名，是不是很聪明？

⚙️ 原理小揭秘：它是“堆”做的

priority_queue 的内部用的是一种叫 堆（heap） 的结构。
它就像一棵神奇的“树”，能让最大（或最小）的数总是在最上面。

比如这组数：5, 2, 8, 1, 9

它会自动排成这样：

      9
     / \
    5   8
   / \
  1   2

top() 一看，就是 9 —— 最大的！

每次 push() 或 pop()，它都能自动调整，让新的堆保持整齐。

🌟 小结：priority_queue 就像一个“聪明的队列”

🏁 最后一个小练习

写个程序，找出一堆数字里的第 k 大的数！

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int n : nums) {
        q.push(n);
        if (q.size() > k) q.pop();
    }
    return q.top();
}

int main() {
    vector<int> nums = {5, 1, 9, 3, 7};
    cout << "第 2 大的数是：" << findKthLargest(nums, 2);
}

输出结果：

第 2 大的数是：7

🎯 总结一句话

priority_queue 是一个会自己“排队”的队列，
谁最大（或最小），谁就最先被看到！

掌握它，就能轻松写出“找最大值”“找最小值”“求前 K 名”的程序。
在 C++ 的世界里，这是一个非常实用又聪明的小工具。