AcWing 839. 模拟堆
原题链接
简单
作者:
从前
,
2021-05-23 13:49:09
,
所有人可见
,
阅读 201
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
//ph[j] = k 第j个插入点的下标是k
int h[N], hp[N], ph[N];
int cnt;
void heap_swap(int a, int b) {
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u) {
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = 2 * u + 1;
if(u != t) {
heap_swap(u, t);
down(t);
}
}
void up (int u) {
while(u / 2 && h[u] < h[u / 2]) {
heap_swap(u,u / 2);
u >>= 1;
}
}
int main() {
int n, m = 0;
scanf("%d",&n);
while(n--) {
string s;
cin >> s;
if(s == "I") {
int x;
scanf("%d",&x);
h[++cnt] = x;
m++;
ph[m] = cnt;
hp[cnt] = m;
up(cnt);
}
else if(s == "PM") {
printf("%d\n",h[1]);
}
else if(s == "DM") {
heap_swap(1,cnt);
cnt--;
down(1);
}
else if(s == "D") {
int k;
scanf("%d", &k);
//k = ph[k];
heap_swap(k,cnt);//来记录第K个插入点的下标是什么。不然交换完就没了
cnt--;
down(k);
up(k);
}
else {
int k, x;
scanf("%d%d", &k, &x);
k = ph[k];//来记录第K个插入点的下标是什么。不然交换完就没了
h[k] = x;
up(k);
down(k);
}
}
return 0;
}