洛谷P3378 【模板】堆 题解 堆（Heap）入门题

题目链接：https://www.luogu.com.cn/problem/P3378

题目大意：维护一个小根堆。

堆的入门题。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int tree[maxn], n, sz, op, x;
void up(int x) {
    while (x != 1 && tree[x] < tree[x/2]) {
        swap(tree[x], tree[x/2]);
        x /= 2;
    }
}
void Insert(int num) {
    tree[++sz] = num;
    up(sz);
}
void down(int x) {
    while (x <= sz) {
        int son = -1;
        if (x*2+1 <= sz && min(tree[x*2], tree[x*2+1]) < tree[x]) {
            if (tree[x*2] <= tree[x*2+1]) son = x*2;
            else son = x*2+1;
        }
        else if (x*2 <= sz && tree[x*2] < tree[x]) {
            son = x*2;
        }
        if (son != -1) {
            swap(tree[x], tree[son]);
            x = son;
        }
        else break;
    }
}
void Delete() {
    tree[1] = tree[sz--];
    down(1);
}
int main() {
    cin >> n;
    while (n --) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            Insert(x);
        }
        else if (op == 2) cout << tree[1] << endl;
        else Delete();
    }
    return 0;
}

洛谷P3378 【模板】堆 题解 堆（Heap）入门题

原文：https://www.cnblogs.com/quanjun/p/12387413.html