堆排序依赖于上午写道的构建堆和调整堆。

基本思想：
(1)首先执行BuildHeap（以最大堆为例），则arr[0]已经是最大元素了，如果我们要按照从小到大排序，那么它应该被放在arr[n-1]上，于是，我们swap arr[0]和arr[n-1]。
(2)类似的，我们让i从n-1到0，依次执行调整堆，AdjustHeap(i,n)，每次调整完成后，堆顶部一定是最大元素，正好把他换到i-2上。
上述的思路和选择排序是不是非常相似！

改进：
调整堆实际用到了递归方法，而其实它是可以非递归化的。非递归化后，性能较递归版本有略微的提升。

全部代码如下：

#include <stdio.h>

typedef long TYPE;

void swap(TYPE* a, TYPE* b)
{
    TYPE tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

//adjust heap()
void heapify(TYPE* heap, int idx, int n)
{
    //left and right index
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    int large = 0;

    //Check left
    if(left<n && heap[left]>heap[idx])
    {
        large = left;
    }
    else
    {
        large = idx;
    }

    //Check right
    if(right<n && heap[right]>heap[large])
    {
        large = right;
    }

    //Swap idx and max one
    if(idx!=large)
    {
        swap(&heap[idx], &heap[large]);
        heapify(heap, large, n);
    }
}

void buildHeap(TYPE* heap, int n)
{
    int i=n/2-1;
    for(; i>=0; i--)
    {
        heapify(heap, i, n);
    }
}

void heapSort(TYPE*heap, int n)
{
    int i;
    buildHeap(heap, n);
    for(i=n-1; i>=1; i--)
    {
        swap(&heap[0], &heap[i]);
        heapify(heap, 0, i);
    }
}

int main()
{
    TYPE arr[16] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    int i;
    int len;

    len = sizeof(arr)/sizeof(TYPE);

    //Test heapify
    //heapify(arr, (len-1)/2, len);
    //buildHeap(arr, len);
    heapSort(arr, len);

    //print
    for(i=0; i<len; i++)
    {
        printf("%ld ", arr[i]);
    }
    printf("\n");

}