【525. 模拟堆】

原题解

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,s;
int h[N];
void down(int u)
{int t=u;if(u*2<=s&&h[u*2]<h[t]) t=u*2;//判断左儿子是否比当前的结点要小if(u*2+1<=s&&h[u*2+1]<h[t]) t=u*2+1;//判断右儿子是否比当前的结点要小if(u!=t){swap(h[t],h[u]);down(t);}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>h[i];s=n;for(int i=n/2;i;i--) down(i);while(m--){cout<<h[1]<<" ";h[1]=h[s];s--;down(1);}return 0;
}作者：Tsukinousag1
链接：https://www.acwing.com/solution/content/9491/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}

#include<bits/stdc++.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
char str[2];
int hp[N],ph[N],h[N];
int SIZE;
void heap_swap(int a,int b)
{
//这里的两个swap先后位置没有影响的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<=SIZE&&h[u*2]<h[t]) t=u*2;if(u*2+1<=SIZE&&h[u*2+1]<h[t]) t=u*2+1;if(t!=u){heap_swap(t,u);down(t);}
}
void up(int u)
{while(u/2&&h[u/2]<h[u]){heap_swap(u/2,u);u/=2;}
}
int main()
{int n,m=0;cin>>n;while(n--){int x,k;cin>>str;if(!strcmp(str,"I")){scanf("%d",&x);SIZE++;m++;hp[SIZE]=m,ph[m]=SIZE;h[SIZE]=x;up(SIZE);}else if(!strcmp(str,"PM"))cout<<h[1]<<endl;else if(!strcmp(str,"DM")){heap_swap(1,SIZE);SIZE--;down(1);}else if(!strcmp(str,"D"))//删除第k个插入的数{scanf("%d",&k);k=hp[k];heap_swap(k,SIZE);up(k);down(k);}else if(!strcmp(str,"C"))//修改第k个数，将其变为x{scanf("%d%d",&k,&x);k=hp[k];h[k]=x;up(k);down(k);}}return 0;
}作者：Tsukinousag1
链接：https://www.acwing.com/solution/content/9491/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。