堆排序

参考资料：
http://www.cnblogs.com/jingmoxukong/p/4303826.html

如果每个节点的关键字都不大于其孩子节点的关键字，称 小根堆；
如果每个节点的关键字都不小于其孩子节点的关键字，称大根堆；

Paste_Image.png

如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个父结点，元素3和元素8。

元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2i+1];
(2) 它的右孩子结点是：R[2i+2];
(3) 它的父结点是：R[(i-1)/2]*;
(4) R[i] <= R[2i+1] 且 R[i] <= R[2i+2]。

算法思路：

按照堆的定义，将数组R[0..n]调整为堆，交换R[0]和R[n];
将R[0..n-1]调整为堆，交换R[0]和R[n-1];
如此反复交换，直到交换了R[0],R[1]为止；

算法操作

1. 根据初始化数组构造初始堆（构建一个完全二叉树，并保证所有的父节点，都比其孩子节点数值大）
2. 每次交换第一个和最后一个元素，并输出最后一个元素（树中的最大值），然后把剩下元素，重新调整为大根堆；
3. 输出完最后一个元素后，数组就排序好了；

实现算法：

// 堆排序* 左子树索引：2n+1* 游子树索引：2n+2* 堆的存储表示是顺序的。* 当想得到一个序列中第k个最小的元素之前的部分排序序列，
// 最好采用堆排序。
public class HeapSort {
    public static void main(String[] args) {
        int[] a = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0, -1};
        System.out.print("排序前： \t\t");
        Utils.printArray(a);

        heapSort(a);
    }

    public static void heapSort(int a[]) {
        //1. 首先，获取该数组的 初始化为大根堆 （父节点，比所有子节点都大）
        //2. 将第一个元素与最后一个元素进行交换
        //3. 去除最后一个元素，并重新调整为大根堆
        //4. 重复2，3，直到最后一个元素输出

        // 从最后一个父节点(length/2)，开始，循环来创建 大根树
        int length = a.length;
        for (int i = length / 2; i >= 0; i--) {
            buildMaxHeap(a, i, length - 1);
        }

        // 打印一下
        Utils.print("初始化堆：\t");
        Utils.printArray(a);

        // 进行 n-1次循环，完成排序，（将不断省略最后一个数）
        for (int i = length - 1; i > 0; i--) {
            // 交换第一个元素与最后一个元素
            int max = a[i];
            a[i] = a[0];
            a[0] = max;

            // 调整，获取i-1个节点的堆
            buildMaxHeap(a, 0, i);

            System.out.format("第%d趟：\t", length - i);
            Utils.printArray(a);
        }
    }

    /**
     * 为数组a，父节点parent，创建大根堆
     *
     * @param a      数组
     * @param parentIndex父节点索引
     * @param length 堆的大小
     */
    public static void buildMaxHeap(int a[], int parentIndex, int length) {
        int currentParentIndex = parentIndex;                // 当前父节点索引
        int parentValue = a[currentParentIndex];        // 父节点值
        int child = currentParentIndex * 2 + 1;            // 左树索引

        // 如果有子树，就不断遍历 (**这段像选择排序**)
        while (child < length) {
            // 如果右树值 > 左树值,child 赋值为右索引
            if (child + 1 < length && a[child + 1] > a[child]) {
                child++;
            }

            // 如果当前父节点值 >= 子树值，表示，不需要查找下去了，退出循环
            if (parentValue >= a[child]) {
                break;
            }

            // 否则，将child值赋给 currentParentIndex 
            a[currentParentIndex] = a[child];

            // 重新赋值 currentParentIndex 与 child
            currentParentIndex = child;
            child = child * 2 + 1;        // 下一个左树
        }

        // 如果currentParentIndex ，被子树索引重新赋值了,
将原始parentValue，赋值给a[currentParentIndex] 
        if (currentParentIndex != parentIndex) {
            a[currentParentIndex] = parentValue;
        }
    }
}