Acwing 838 堆排序

Acwing 838 堆排序

#include <iostream>
#include <cstdio>
using namespace std;
int m,n;
#define MAXN 100010
int a[MAXN];
int size;

void down(int u){
    int t = u;
    if(u*2<=size && a[u*2]<a[t]) t = u*2;
    if(u*2+1<=size && a[u*2+1]<a[t]) t = u*2+1;
    if(u!=t){
        swap(a[u],a[t]);
        down(t);
    }
}


int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    size = n;
    for(int i=n/2;i;i--){
        down(i);
    }
    while(m--){
        printf("%d ",a[1]);
        a[1] = a[size];
        size--;
        down(1);
    }


    return 0;
}