題目鏈接
https://www.luogu.org/problem/P3378
分析
基本的堆操作，優(yōu)先隊(duì)列也可過，但手寫堆速度更快绿映，且可支持修改操作扛芽，因而用于優(yōu)化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;
}
