堆

堆排序

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(n) scanf("%d",&n)
#define print(n) printf("%d\n",n)
#define endl "\n";
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int N=1000001;
const int MOD = 1e9 + 7;
const int INF=1e9;
const double eps=1e-5;
int a[N],sum[N];
int n,m,k,cnt;

void down(int x){
    int t=x;
    if(x*2<=cnt&&a[x*2]<a[t]) t=x*2;
    if(x*2+1<=cnt&&a[x*2+1]<a[t]) t=x*2+1;//t改变最大值，所以比较要用t
    if(x!=t){
        swap(a[x],a[t]);
        down(t);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    cnt = n;

    for (int i = n / 2; i; i -- ) down(i);

    while (m -- )
    {
        printf("%d ", a[1]);
        a[1] = a[cnt -- ];
        down(1);
    }

    puts("");

    return 0;
}