[DOJ练习] 堆排序验证性实验

请创建一个一维整型数组用来存储待排序关键码，关键码从数组下标为1的位置开始存储，下标为0的位置不存储关键码。输入关键码的个数，以及各个关键码，采用堆排序的方法对关键码数组进行排序，输出初始堆序列，以及每轮调整堆的关键码比较过程。

输入描述
各个命令以及相关数据的输入格式如下：

第一行输入关键码的个数n

第二行输入n个整型关键码

输出描述
首先输出建初始堆的过程，输出要与双亲结点交换的根结点的关键码，每棵子树的调整占一行。

接下来一行输出初始堆序列。

接下来若干行输出关键码比较过程，输出要与双亲结点交换的根结点的关键码，每轮调整堆一行，关键码之间以空格隔开，最后一个关键码后有空格，然后回车，不重复输出。

最后输出排好序的关键码，以空格隔开，最后回车。

输入样例
10
2 5 9 8 7 4 3 10 16 13
输出样例
13
16
16 10
16 13 7
16 13 9 10 7 4 3 5 8 2
13 10 8
10 8 5
9 4
8 7
7 5
5 
4 
3 
2 3 4 5 7 8 9 10 13 16 

#include <iostream>
using namespace std;

const int N = 1010;
int n,h[N];

void fall(int u,int len){
    int t = h[u];
    int L = u << 1;
    for(int i = L; i <= len; i <<= 1){
        if(i < len && h[i]<h[i + 1]) i++;
        if(h[i] <= t) break;

		h[u] = h[i];
        u = i;
        cout << h[u] << ' ';    
    }
    //cout<<endl;
    h[u] = t;
}

void heapSort(){
    for(int i = n/2; i > 0; i --) fall(i, n);
    for(int i = 1; i <= n; i ++) cout << h[i] << ' ';

    for(int i = n; i > 0; i --){
        swap(h[1], h[i]);
        fall(1, i-1);
    }
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> h[i];
    
    heapSort();
    for(int i = 1; i <= n; i ++) cout << h[i] << ' ';

    return 0;
}