堆排序

堆分为最大堆和最小堆

最大堆

定义：设数组a存放了n个数据元素，数组下标从0开始，如果当数组下标2i+1<n时存在a[i].key>a[2i+1].key>=a[i].key，当数组下标2i+2<n时，有a[i].key>=a[2i+2].key，这样的数据结构称为最大堆。

最大堆的根节点是堆值中最大的数据元素。

对于最大堆，从根结点到每个叶结点的路径，数组元素组成的序列都是递减有序的

通常把堆的根节点称为堆顶元素。

最小堆（与最大堆类似，这里不再累赘）

创建堆

在完全二叉树中，第一个非叶子结点a[i] (i = (n - 2) / 2)

创建思路：从第一个非叶子结点开始，找出a[2i+1]和a[2i+2]的最大值，并与a[i]进行比对，若比a[i]小，则说明以a[i]为更结点的堆已经是最大堆，否则，二者交换。以此类推，直到调整到根节点。

值得注意的是：若左右子节点并非叶子结点，与a[i]的调换可能会引起子节点的一连串调整，这也是值得我们注意的地方

/**
 * @param data 待排序的数组
 * @param n    元素的总个数
 * @param h    当前的根节点
 */
void createHeap(int[] data, int n, int h) {
    int i = h;
    int j = 2 * i + 1;
    int temp = data[i];

    while (j < n) {

        // 寻找左右子节点的最大值
        if (j + 1 < n && data[j] < data[j + 1]) j++;

        // 对比根节点与左右子节点的最大值
        if (temp > data[j]) {
            break;
        } else {
            data[i] = data[j];
            i = j;
            j = 2 * i + 1;
        }
    }
    data[i] = temp;
}

void initHeap(int[] data, int n) {
    for (int i = (n - 2) / 2; i > -1; i--) {
        createHeap(data, n, i);
    }
}

利用最大堆来进行排序

void heapSort(int[] data, int n) {
    initHeap(data, n);

    for (int i = n - 1;i > -1;i--) {
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
        createHeap(data, i, 0);
    }
}