AcWing 839. 模拟堆
原题链接
简单
作者:
dsyami
,
2021-05-14 15:21:37
,
所有人可见
,
阅读 238
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], mysize;
int hp[N], ph[N];
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 i)
{
int u = i;
if(i * 2 <= mysize && h[i * 2] < h[u]) u = i * 2;
if(i * 2 + 1 <= mysize && h[i * 2 + 1] < h[u]) u = i * 2 + 1;
if(u != i)
{
heap_swap(i, u);
down(u);
}
}
void up(int i)
{
while(i / 2 && h[i / 2] > h[i])
{
heap_swap(i, i / 2);
i /= 2;
}
}
int front()
{
return h[1];
}
void pop()
{
heap_swap(1, mysize);
mysize --;
down(1);
}
int main()
{
int n, k, x;
string op;
cin >> n;
int cnt = 0;
while(n -- )
{
cin >> op;
if(op == "I")
{
cin >> x;
++ cnt;
h[++ mysize] = x;
hp[mysize] = cnt;
ph[cnt] = mysize;
up(mysize);
}
else if(op == "PM") cout << front() << endl;
else if(op == "DM") pop();
else if(op == "D")
{
cin >> k;
int temp = ph[k]; //设置临时变量
heap_swap(temp, mysize);
mysize --;
down(temp), up(temp); //参数不能直接用ph[k],因为在进行heap_swap时改变了ph[k]的值
}
else if(op == "C")
{
cin >> k >> x;
int temp = ph[k];
h[temp] = x;
down(temp), up(temp);
}
}
return 0;
}