在上篇文章中已經(jīng)講過了什么是二叉堆。那么這個二叉堆怎樣使用呢？so，這篇文章講講堆排序。

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

• 二叉堆實際上是一個完全二叉樹
• 最小堆的堆頂是整個堆中的最小元素
• 最大堆的堆頂是整個堆中的最大元素

二叉堆的自我調整

因為二叉堆的自我調整，當我們把一個最大堆的堆頂元素與最后一個元素交換，經(jīng)過自我調整，第二大的元素就會成為新堆頂。
由于二叉堆的這個特性，我們每次交換堆頂，調整后的新堆頂都是大小僅次于舊堆頂?shù)墓?jié)點。那么我們只要反復的交換，經(jīng)過反復調整二叉堆。最終就能得到一個有序的集合。

由此，我們可以歸納出堆排序算法的步驟：

• 把一個無序數(shù)組構建成一個二叉堆
• 循環(huán)把堆頂元素移到尾部，調整產(chǎn)生新的堆頂

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) {
        // 左子節(jié)點下標
        int childIndex = 2 * parentIndex + 1;
        int temp = array[parentIndex];
        while (childIndex < arrLength) {
            // 如果有右節(jié)點，且右節(jié)點小于左節(jié)點
            if (childIndex + 1 < arrLength && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            // 如果父節(jié)點小于兩個子節(jié)點
            if (temp < array[childIndex])
                break;
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }