AcWing 838. 堆排序
原题链接
简单
#include<iostream>
using namespace std;
//难点1:维护堆序性跟堆排序是不一样的。堆排序更苛刻。
//难点2:讨论节点有没有右子。
//难点3:使用up从后向前遍历跟使用down从前向后遍历是一样的吗?
const int N=100010;
int a[N];
void down(int i,int n){
int tmp;
while(i<<1+1<=n){
if(a[i]>a[i<<1] || a[i]>a[i<<1+1]){
if(a[i<<1]>a[i<<1+1]){
tmp=a[i<<1];
a[i<<1]=a[i];
a[i]=tmp;
i=i<<1;
}
else if(a[i]>a[i<<1+1]){
tmp=a[i];
a[i]=a[i<<1+1];
a[i<<1+1]=tmp;
i=i<<1+1;
}
}
}
if(i>>1 != n && a[i]>a[i<<1]){//没有右子
tmp=a[i];
a[i]=a[i<<1];
a[i<<1]=tmp;
i=i<<1;
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
//堆排序
for(int i=1;i<=n;i++){
down(i,n);
}
for(int i=1;i<=m;i++){
printf("%d ",a[i]);
}
return 0;
}