AcWing 839. 模拟堆
原题链接
简单
作者:
术
,
2021-01-09 16:26:52
,
所有人可见
,
阅读 241
#include <iostream>
using namespace std;
const int N=100005;
int heap[N];
int ph[N];//映射 第几个数和size
int hp[N];//交换ph时使用,互相映射
int Size;
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);//可以换顺序
swap(hp[a],hp[b]);
swap(heap[a],heap[b]);
}
void down(int u)
{
int t=u;
if(u*2<=Size&&heap[u*2]<heap[t])
t=u*2;
if(u*2+1<=Size&&heap[u*2+1]<heap[t])
t=u*2+1;
if(u!=t)
{
heap_swap(u,t);
down(t);
}
}
void up(int u)
{
while(u/2&&heap[u/2]>heap[u])
{
heap_swap(u/2,u);
up(u/2);
}
}
int main()
{
int n;
cin>>n;
int cnt=0;
while(n--)
{
char op[5];
scanf("%s",op);
if(op[0]=='I')
{
int x;
cin>>x; //cout<<x<<endl;
Size++;
cnt++;
ph[cnt]=Size;
hp[Size]=cnt;//size x可能会重复
heap[Size]=x;
up(Size);
}
else if(op[0]=='P'&&op[1]=='M')
{
cout<<heap[1]<<endl;
}
else if(op[0]=='D'&&op[1]=='M')
{
heap_swap(1,Size);
Size--;
down(1);
}
else if(op[0]=='D')
{
int k;
cin>>k;
k=ph[k];
heap_swap(k,Size);
Size--;
down(k);
up(k);
}
else
{
int k,x;
cin>>k>>x;
k=ph[k];
heap[k]=x;
down(k);
up(k);
}
}
//cout << "Hello world!" << endl;
return 0;
}