AcWing 839. 模拟堆
原题链接
简单
作者:
szywdwd
,
2021-05-24 15:51:00
,
所有人可见
,
阅读 177
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], sizeOfHeap;
int ph[N];// 存储第k个插入的点在堆中的位置
int hp[N];// 存储堆中下标是i的点是第几个插入的
int K;
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 <= sizeOfHeap && h[t] > h[u * 2] ) t = u * 2;
if(u * 2 + 1 <= sizeOfHeap && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
if(t != u) {
heap_swap(t, u);
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;
cin >> n;
while(n--) {
char op[3];
cin >> op;
if(op[0] == 'I') {
int x;
cin >> x;
++sizeOfHeap, ++K;
ph[K] = sizeOfHeap;
hp[sizeOfHeap] = K;
h[sizeOfHeap] = x;
up(sizeOfHeap);
}
else if(op[0] == 'P' && op[1] == 'M') {
cout << h[1] << endl;
}
else if(op[0] == 'D' && op[1] == 'M') {
heap_swap(1, sizeOfHeap);
--sizeOfHeap;
down(1);
}
else if(op[0] == 'D') {
int k;
cin >> k;
k = ph[k];
heap_swap(k, sizeOfHeap);
--sizeOfHeap;
down(k);
up(k);
}
else if(op[0] == 'C') {
int k, x;
cin >> k >> x;
k = ph[k];
h[k] = x;
down(k);
up(k);
}
}
return 0;
}