优先队列 与 二叉堆 全解析

const int N = 1000005;
int h[N], sz = 0;              // h[1..sz] 为堆，h[0] 空着不用

// 上浮：与父亲比较，比自己小就交换，一路上顶
void shift_up(int i) {
    while (i > 1 && h[i] > h[i >> 1]) {   // i >> 1 等价于 i / 2
        swap(h[i], h[i >> 1]);
        i >>= 1;
    }
}

// 下沉：与「较大的那个儿子」比较，比自己大就交换，一路下沉
void shift_down(int i) {
    while ((i << 1) <= sz) {                // 只要还有左儿子
        int s = i << 1;                     // s = 左儿子
        if (s + 1 <= sz && h[s + 1] > h[s]) s++;   // 选出较大的儿子
        if (h[i] >= h[s]) break;             // 已经满足堆序，收工
        swap(h[i], h[s]);
        i = s;                              // 继续往下检查
    }
}

void push(int x) { h[++sz] = x; shift_up(sz); }
int  top()  { return h[1]; }
void pop()  { h[1] = h[sz--]; shift_down(1); }

总代价 ≤ Σ(h 从 0 到 log n) h · n / 2^(h+1) = (n/2) · Σ h / 2^h ≤ (n/2) · 2 = n

// ---------- 写法 A：逐个插入，O(n log n) ----------
for (int i = 1; i <= n; i++) { h[++sz] = x[i]; shift_up(sz); }

// ---------- 写法 B：倒着下沉，O(n) ----------
for (int i = 1; i <= n; i++) h[i] = x[i];
sz = n;
for (int i = n / 2; i >= 1; i--) shift_down(i);   // 从最后一个非叶节点倒着来

// ---------- 应用：堆排序（升序输出） ----------
for (int i = 1; i <= n; i++) {
    printf("%d ", h[1]);     // 取堆顶（当前最大值）
    h[1] = h[sz--];           // 末尾补位
    shift_down(1);            // 维护堆序
}

#include <queue>
priority_queue<int> pq;              // 等价于 priority_queue<int, vector<int>, less<int>>
pq.push(3); pq.push(1); pq.push(9);
printf("%d\n", pq.top());          // 9，队首是最大值

priority_queue<int, vector<int>, greater<int> > pq;   // 两个 > 之间要有空格
pq.push(3); pq.push(1); pq.push(9);
printf("%d\n", pq.top());          // 1，队首是最小值

struct Node {
    int id, val;
    // 注意：priority_queue 默认用 less，返回 true 表示「优先级更低」
    // 想让 val 大的优先 → 让 val 小的「优先级更低」→ 返回 a.val < b.val
    bool operator<(const Node& o) const {
        if (val != o.val) return val < o.val;   // val 大的先出
        return id > o.id;                       // val 相同时 id 小的先出
    }
};
priority_queue<Node> pq;

struct Node { int id, val; };

struct cmp {
    bool operator()(const Node& a, const Node& b) const {
        if (a.val != b.val) return a.val > b.val;   // 注意：写 > 才是 val 小的先出
        return a.id < b.id;
    }
};
priority_queue<Node, vector<Node>, cmp> pq;   // 队首：val 最小者

// ---- pair 进堆：默认先比 first，first 相同比 second，都是「大的优先」----
priority_queue<pair<int,int> > pq;
pq.push({3, 100});
pq.push({5, 2});
printf("(%d,%d)\n", pq.top().first, pq.top().second);   // (5,2)
// 想按 first 升序？把 first 取负存进去即可：push({-x, y})

// ---- 懒惰删除：需要「删除堆中某个元素」但堆不支持删除中间元素 ----
// 做法：不真删，只是打个标记；等它浮到堆顶时再顺手扔掉
int del[N];                        // del[x] = x 被删了几次
while (!pq.empty() && del[pq.top()]) { del[pq.top()]--; pq.pop(); }
int now = pq.top();                // 此时堆顶才是有效的最大值

priority_queue<int> L;                              // 大根堆：较小的一半
priority_queue<int, vector<int>, greater<int> > R;   // 小根堆：较大的一半

void add(int x) {
    // ① 决定进哪边
    if (L.empty() || x <= L.top()) L.push(x);
    else                           R.push(x);

    // ② 调整数量，维持 size(L) == size(R) 或 size(L) == size(R)+1
    if ((int)L.size() > (int)R.size() + 1) { R.push(L.top()); L.pop(); }
    if ((int)R.size() > (int)L.size())      { L.push(R.top()); R.pop(); }
}
int median() { return L.top(); }             // ③ 查询 O(1)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int> > pq;   // 小根堆
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &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);                    // 合并后的新堆放回
    }
    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, A[N], B[N];

struct Node {
    int sum, i, j;                 // 和、行号、列号
    // 小根堆：让 sum 小的「优先级更高」→ 让 sum 大的「优先级更低」
    bool operator<(const Node& o) const { return sum > o.sum; }
};
priority_queue<Node> pq;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &B[i]);

    // 每行的第 1 个元素入堆
    for (int i = 1; i <= n; i++) pq.push({A[i] + B[1], i, 1});

    for (int k = 1; k <= n; k++) {
        Node t = pq.top(); pq.pop();
        printf("%d ", t.sum);
        if (t.j + 1 <= n)                       // 顺着这一行往右推
            pq.push({A[t.i] + B[t.j + 1], t.i, t.j + 1});
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 200005, INF = 0x3f3f3f3f;
int n, m, s;
int head[N], nxt[M], to[M], w[M], ec = 0;
int dist[N];
bool vis[N];

void add(int u, int v, int c) { to[++ec] = v; w[ec] = c; nxt[ec] = head[u]; head[u] = ec; }

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++) {
        int u, v, c; scanf("%d%d%d", &u, &v, &c);
        add(u, v, c);
    }

    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;

    // pair 默认按 first 降序 → 存 -dist 就变成「dist 小的优先」
    priority_queue<pair<int,int> > pq;
    pq.push({0, s});

    while (!pq.empty()) {
        int d = -pq.top().first, u = pq.top().second;
        pq.pop();

        // 懒惰删除：这是「过期的旧记录」，直接跳过
        if (d > dist[u]) continue;

        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (dist[u] + w[e] < dist[v]) {       // 松弛成功
                dist[v] = dist[u] + w[e];
                pq.push({-dist[v], v});              // 新记录入堆
            }
        }
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", dist[i] == INF ? 2147483647 : dist[i]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    priority_queue<int> L;                              // 大根堆：较小的一半
    priority_queue<int, vector<int>, greater<int> > R;   // 小根堆：较大的一半

    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);

        // ① 决定进哪边
        if (L.empty() || x <= L.top()) L.push(x);
        else                           R.push(x);

        // ② 调整数量
        if ((int)L.size() > (int)R.size() + 1) { R.push(L.top()); L.pop(); }
        if ((int)R.size() > (int)L.size())      { L.push(R.top()); R.pop(); }

        // ③ 奇数位置输出中位数
        if (i % 2 == 1) printf("%d\n", L.top());
    }
    return 0;
}

typedef pair<long long, int> PII;   // (权值, 深度)
priority_queue<PII, vector<PII>, greater<PII> > pq;   // 小根堆，权值相同时深度小的优先

for (int i = 1; i <= n; i++) pq.push({w[i], 0});

// 补虚节点：让 (n-1) 能整除 (k-1)
while ((pq.size() - 1) % (k - 1) != 0) pq.push({0, 0});

long long ans = 0; int maxd = 0;
while (pq.size() > 1) {
    long long s = 0; int d = 0;
    for (int i = 0; i < k; i++) {          // 取出最小的 k 个
        s += pq.top().first;
        d = max(d, pq.top().second);
        pq.pop();
    }
    ans += s;
    maxd = max(maxd, d + 1);
    pq.push({s, d + 1});                  // 新节点深度 = 子树最大深度 + 1
}
printf("%lld\n%d\n", ans, maxd);

priority_queue<PII, vector<PII>, greater<PII> > pq;   // (边权, 点)
pq.push({0, 1});                                    // 任选 1 号点作起点
int cnt = 0; long long ans = 0;

while (!pq.empty() && cnt < n) {
    int d = pq.top().first, u = pq.top().second; pq.pop();
    if (vis[u]) continue;          // 懒惰删除：已加入的点直接跳过
    vis[u] = true; cnt++; ans += d;

    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (!vis[v]) pq.push({w[e], v});     // 把与 u 相连的边都入堆
    }
}
if (cnt < n) puts("orz");        // 图不连通，无生成树
else         printf("%lld\n", ans);

int h[N], sz = 0;

void shift_up(int i) {
    while (i > 1 && h[i] > h[i >> 1]) { swap(h[i], h[i >> 1]); i >>= 1; }
}
void shift_down(int i) {
    while ((i << 1) <= sz) {
        int s = i << 1;
        if (s + 1 <= sz && h[s + 1] > h[s]) s++;      // 选较大的儿子
        if (h[i] >= h[s]) break;
        swap(h[i], h[s]); i = s;
    }
}
void push(int x) { h[++sz] = x; shift_up(sz); }
int  top()  { return h[1]; }
void pop()  { h[1] = h[sz--]; shift_down(1); }
// 建堆：for (int i = n/2; i >= 1; i--) shift_down(i);   O(n)
// 小根堆：把所有比较符号反向（> 变 <，选较小的儿子）