AcWing 838. 堆排序

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int q[N],num;
void down(int u){
    int t = u;
    if(u * 2 <= num && q[u * 2] < q[t]) t = u * 2;
    if(u * 2 + 1 <= num && q[u * 2 + 1] < q[t]) t = u * 2 + 1;
    if(u != t){
        swap(q[u],q[t]);
        down(t);
    }  
}
/*
down()
*/
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> q[i];
    num = n;
    for(int i = n / 2; i; i--) down(i);
    while(m--){
        cout << q[1] << ' ';
        q[1] = q[num];
        num --;
        down(1);
    }
    return 0;
}