堆 / 优先队列CSP-J

💡 核心思想

堆是一种特殊的完全二叉树，满足堆性质：大根堆中每个节点的值 ≥ 子节点的值。C++ STL 的 priority_queue 默认是大根堆。支持 $O(\log n)$ 插入和取出最值，$O(1)$ 查看最值。常用于 Dijkstra、贪心、Top-K 等问题。

🎯 直觉理解

堆就像一个"自动排序"的队伍。无论你什么时候加人进来，最厉害的那个人（大根堆）或最弱的那个（小根堆）永远在最前面。你想找最值不用翻遍整个队伍，直接看第一个就行。

📝 算法流程

1. C++ 默认大根堆：priority_queue
2. 小根堆：priority_queue, greater>
3. push：$O(\log n)$ 插入
4. pop：$O(\log n)$ 取出最值

$$\text{堆操作：插入/删除 } O(\log n)，\text{取最值 } O(1)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
    for (int i = 0; i < n; i++) { int x; cin >> x; pq.push(x); }
    long long ans = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans << endl; // 合并果子
    return 0;
}

⚠️ 常见坑点

📚 相关题目