洛谷 P3378 【模板】堆

题目链接

https://www.luogu.org/problem/P3378

分析

基本的堆操作，优先队列也可过，但手写堆速度更快，且可支持修改操作，因而用于优化Dijkstra算法效率更高。

AC代码

#include <cstdio>
#include <iostream>

using namespace std;

inline int get_num() {
    int num = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9')
        num = num * 10 + c - '0', c = getchar();
    return num;
}

const int maxn = 1e6 + 5;

int heap[maxn], len;

inline void insert(int x) {
    heap[++len] = x;
    int pos = len;
    while (pos > 1 && heap[pos] < heap[pos / 2])
        swap(heap[pos], heap[pos / 2]), pos /= 2;
}

inline void pop() {
    heap[1] = heap[len--];
    int pos = 1;
    while (pos * 2 <= len) {
        int next = pos * 2;
        if (next + 1 <= len && heap[next + 1] < heap[next]) ++next;
        if (heap[next] < heap[pos])
            swap(heap[next], heap[pos]), pos = next;
        else break;
    }
}

int main() {
    int n = get_num();
    for (int i = 1; i <= n; ++i) {
        int op = get_num();
        if (op == 1) insert(get_num());
        else if (op == 2) printf("%d\n", heap[1]);
        else pop();
    }
    return 0;
}