第一次接触到堆排序的时候，感觉堆排序很美，因为它将一个一维度的数据结构抽象成了一个二维的数据结构，在空间上给人以更多遐想，也带来更多的可能。

什么是堆呢？有这样一种二叉树状结构，他的每一个父节点都大于等于所有的子节点，我们把这个二叉树结构用一个一维数组存储，将这棵树从上往下、从左往右，从1开始一直数数，直到最后一个节点n，每个节点的数字就是他们在一维数组中的编号。

你发现了什么吗？这棵树提供了什么信息？这棵树最高的那个顶点就是最大的数字，而把一个无序的一维数组构建成这样一颗树的过程就是堆化。

那如何排序呢？

我们将最大的数字拿下来，同时将数组末尾的数字放到顶部，然后再次运行堆化算法，顶部的数字又是剩余数字的最大数字了，我们又取下来，如此往复，直到数组无序的部分变为空为止，排序完毕。

在完成这个算法时需要注意一些隐含的信息。
1、完全二叉树状结构的特性：下标为x的节点，其子节点的下标分别为2x和2x+1
2、堆化完成后顶点的值最大，每次只完成对一个数字的排序

void sort(int *arr, int len)
{
    //初始化堆
    sink(arr, (len - 1)/2, len);
    while (len > 0)
    {
        exchange(arr, 1, len);
        len--;
        sink(arr, 1, len);
    }
        
}

void sink(int *arr, int k, int len)
{
    for(int i = k; i > 0; i--)
    {
        int key = i;
        while(key > 0)
        {
            int lc = 2 * key;
            int rc = 2 * key + 1;
            int max = 0;
            (lc <= len) && (max = lc);
            (rc <= len) && (arr[rc] > arr[lc]) && (max = rc);

            if(max > 0 && arr[max] > arr[key])
            {
                exchange(arr, max, key);
                key = max;
            } else {
                key = 0;
            }
        }
    }
}