acwing838. 堆排序

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,a[N],cnt;
void down(int x){
    int u=x;
    if(2*x<=cnt&&a[2*x]<a[u])u=2*x;
    if(2*x+1<=cnt&&a[2*x+1]<a[u])u=2*x+1;
    if(u!=x){
        swap(a[u],a[x]);
        down(u);
    }
}
int main(){
    cin>>n>>m;
    cnt=n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n/2;i;i--)down(i);
    while(m--){
        cout<<a[1]<<" ";
        a[1]=a[cnt--];
        down(1);
    }
    
    
    return 0;
}