堆排序

在上篇文章中已经讲过了什么是二叉堆。那么这个二叉堆怎样使用呢？so，这篇文章讲讲堆排序。

首先回顾一下二叉堆的特性：

• 二叉堆实际上是一个完全二叉树
• 最小堆的堆顶是整个堆中的最小元素
• 最大堆的堆顶是整个堆中的最大元素

二叉堆的自我调整

因为二叉堆的自我调整，当我们把一个最大堆的堆顶元素与最后一个元素交换，经过自我调整，第二大的元素就会成为新堆顶。
由于二叉堆的这个特性，我们每次交换堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复的交换，经过反复调整二叉堆。最终就能得到一个有序的集合。

由此，我们可以归纳出堆排序算法的步骤：

• 把一个无序数组构建成一个二叉堆
• 循环把堆顶元素移到尾部，调整产生新的堆顶

Talk is cheap , show me the code.

    /**
     * 堆排序
     */
    private static void heapSort(int[] array) {
        // 构建堆
        buildHeap(array);
        int arrLength = array.length;
        for (int i = arrLength - 1; i > 0; i--) {
            // 交换元素
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            // 下沉调整
            downAdjust(array, 0, i);
        }
    }

    /**
     * 构建堆
     */
    private static void buildHeap(int[] array) {
        int arrLength = array.length;
        for (int i = arrLength / 2; i >= 0; i--) {
            downAdjust(array, i, arrLength);
        }
    }

    /**
     * 下沉调整
     */
    private static void downAdjust(int[] array, int parentIndex, int arrLength) {
        // 左子节点下标
        int childIndex = 2 * parentIndex + 1;
        int temp = array[parentIndex];
        while (childIndex < arrLength) {
            // 如果有右节点，且右节点小于左节点
            if (childIndex + 1 < arrLength && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            // 如果父节点小于两个子节点
            if (temp < array[childIndex])
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }