AcWing 838. 堆排序
原题链接
简单
作者:
术
,
2021-01-08 14:26:09
,
所有人可见
,
阅读 410
#include <iostream>
using namespace std;
const int N=100005;
int heap[N];
int Size;
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){
swap(heap[u],heap[t]);
down(t);
}
}
void up(int u){
while(u/2&&heap[u/2]>heap[u]) {
swap(heap[u/2],heap[u]);
up(u/2);
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>heap[i];
up(i);
Size++;
}
/*Size=n;
for(int i=n;i>=1;i){//从底层开始down
down(i);
}*/
for(int i=1;i<=m;i++){
cout<<heap[1]<<" ";
heap[1]=heap[Size--];
down(1);
}
//cout << "Hello world!" << endl;
return 0;
}