堆可以看成是将一个完全二叉树从上到下，从左到右对每个结点编号，然后对应到一个数组中去，这个完全二叉树要满足任意一个结点的值总是大于或小于其左右子结点的值，对应到数组序列a1，a2，…ak，则要满足

a[i] >= a[2 * i]
a[i] >= a[2 * i + 1]
i = 1，2，...k/2
或
a[i] <= a[2 * i]
a[i] <= a[2 * i + 1]
i = 1，2，...k/2

注意，这里的i表示第几个元素，从1开始，不是数组从0开始的数组下标

假设有a1，a2，…an，初始为一个小顶堆，即a1是最小值
现在将a1的值增大，若要使该序列仍为小顶堆，则要进行筛选
筛选的过程就是将a1与其左右子节点a2，a3比较，将a1，a2，a3重新变成小顶堆，例如a3最小，则a3与a1交换
交换后，可能会破坏a3，a6，a7这个堆，则再进行比较，选出最小的重新构建小顶堆
依次类推，直到整个序列变为小顶堆
上述过程就是一趟筛选

堆排序思路就是
1.从最后一个非终端结点an/2开始，向前遍历，对每个结点进行一趟筛选，直到a1筛选完成，整个序列就变为一个大顶堆(小顶堆)
2.将堆顶元素和第n个元素交换，则第n个元素确定了，但此时a1到an-1的堆被破坏了，然后对a1进行筛选，将a1到an-1重新变成大顶堆(小顶堆)
3.将堆顶元素和第n-1个元素交换，则第n-1个元素确定了，但a1到an-2的堆被破坏了，然后对a1进行筛选，将a1到an-2重新变成大顶堆(小顶堆)
4.以此类推，每次可以确定一个元素的位置，直到整个序列有序

#include<stdio.h>
#define ARRAY_SIZE 9

void swap(int *array, int index1, int index2)
{
        int temp = 0;

        if (!array)
        {
                return;
        }

        temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
}

/* 需要注意传入的low和high是二叉树的结点编号，数组需要减1使用 */
void headAdjust(int *arr, int low, int high)
{
        int i = 0;
        int curVal = 0;

        if (!arr)
        {
                return;
        }

        curVal = arr[low - 1];

        /* 遍历时类似树，i每次乘以2 */
        for (i = 2 * low; i <= high; i *= 2)
        {
                if (i < high && arr[i - 1] < arr[i])
                {
                        i++;
                }

                if (arr[i - 1] < curVal)
                {
                        break;
                }

                arr[low - 1] = arr[i - 1];
                low = i;
        }

        arr[low - 1] = curVal;
}

void heapSort(int *arr, int size)
{
        int i = 0;

        /* 从最后一个非终端结点建堆 */
        for (i = size / 2; i >= 1; i--)
        {
                headAdjust(arr, i, size);
        }

        /* 从size - 1到1，每次确定一个位置，确定第一个时
         * 第0个也好了 */
        for (i = size - 1; i >= 1; i--)
        {
                swap(arr, 0, i);
                headAdjust(arr, 1, i);
        }

}
int main(void)
{
        int i = 0;
        int array[ARRAY_SIZE] = {3, 2, 3, 1, 2, 4, 5, 5, 6};

        heapSort(array, ARRAY_SIZE);

        for (i = 0; i < ARRAY_SIZE; i++)
        {
                printf("%d ", array[i]);
        }

        puts("");

        return 0;
}

O(nlogn)，建立堆是O(n)

O(1)

1.不稳定排序，如7，6，6
2.每次确定一个元素