堆排序的步骤

1) 建堆;
2）输出堆顶的值；
3) 把最后一个值放到1号位，并去掉最后一个位置，然后down(1)。
4)重复 2)~3)直到堆为空。

down操作

从传入的位置开始，不断的比较和结点和两个儿子结点之间的大小，如果比儿子小，那么和儿子交换并继续从该儿子的位置比较，否则就停止。

#include<iostream>

using namespace std;

const int N=1e5+10;

int heap[N],cnt=1;

void down(int i){
    int t=i;//记录的是父亲和左右儿子中最小的那一个的下标
    if(2*i<=cnt&&heap[2*i]<heap[t]) t=2*i;
    if(2*i+1<=cnt&&heap[2*i+1]<heap[t]) t=2*i+1;
    if(i!=t){
        swap(heap[i],heap[t]);
        down(t);
    } 
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&heap[i]);
    cnt=n;
    for(int i=n/2;i;i--) down(i);//据说这样可以把建堆的时间复杂度降到O(n)

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