堆排序（数组模拟堆）（acwing）

解题思路:    首先初始化堆（从小到大），然后每次输出堆首元素 

注意事项:    更新堆时要注意比较的方式

参考代码:

#include<iostream>
using namespace std;
const int N=100010;
int heap[N],n,sizea;
void down(int k)
{
    int t=k; 
    // 注意最后比较要用heap[t]
    if(2*k<=sizea&&heap[2*k]<heap[t])     //左儿子存在并且左儿子的值小
        t=2*k;
    if(2*k+1<=sizea&&heap[2*k+1]<heap[t])    //右儿子存在并且右儿子的值小
        t=2*k+1;
    if(t!=k){
        swap(heap[k],heap[t]);      //存在某个儿子的值小  交换
        down(t);  //递归下去
    }

}
int main(void)
{
    cin>>n;
    sizea=n;
    for(int i=1;i<=n;i++)
        cin>>heap[i];
    for(int i=n/2;i;i--)
        down(i);                 //初始化堆
        while(n--)
        {
            cout<<heap[1]<<' ';    //heap[1]即为栈中最小的
            //删除heap[1] 更新堆
            heap[1]=heap[sizea];
            sizea--;
            down(1);
        }
        cout<<endl;
    return 0;
}