摘要：概述堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。稱這個(gè)過程為堆排序。步驟實(shí)例實(shí)現(xiàn)堆排序需解決兩個(gè)問題如何將個(gè)待排序的數(shù)建成堆輸出堆頂元素后，怎樣調(diào)整剩余個(gè)元素，使其成為一個(gè)新堆。

堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。

堆的定義如下：具有n個(gè)元素的序列(k1,k2,...,kn), 當(dāng)且僅當(dāng)滿足:

時(shí)稱之為堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最小項(xiàng)（小頂堆）或最大項(xiàng)（大頂堆）。

若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)（有子女的結(jié)點(diǎn)）的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的。

(a)大頂堆序列：(96, 83, 27, 38, 11, 09)

(b)小頂堆序列：(12, 36, 24, 85, 47, 30, 53, 91)

初始時(shí)把要排序的n 個(gè)數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹（一維數(shù)組存儲(chǔ)二叉樹），調(diào)整它們的存儲(chǔ)序，使之成為一個(gè)堆，將堆頂元素輸出，得到n 個(gè)元素中最小(或最大)的元素。然后對(duì)剩下的n-1個(gè)元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個(gè)元素中次小(或次大)的元素。依此類推，直到最后得到有n個(gè)節(jié)點(diǎn)的有序序列。稱這個(gè)過程為堆排序。

實(shí)現(xiàn)堆排序需解決兩個(gè)問題：

如何將n 個(gè)待排序的數(shù)建成堆；

輸出堆頂元素后，怎樣調(diào)整剩余n-1 個(gè)元素，使其成為一個(gè)新堆。

建堆方法（小頂堆）：

對(duì)初始序列建堆的過程，就是一個(gè)反復(fù)進(jìn)行篩選的過程。

n 個(gè)結(jié)點(diǎn)的完全二叉樹，則最后一個(gè)結(jié)點(diǎn)是第n/2個(gè)結(jié)點(diǎn)的子樹。

篩選從第n/2個(gè)結(jié)點(diǎn)為根的子樹開始（n/2是最后一個(gè)有子樹的結(jié)點(diǎn)），使該子樹成為堆。

之后向前依次對(duì)各結(jié)點(diǎn)為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)。

如圖建堆初始過程

無序序列：(49, 38, 65, 97, 76, 13, 27, 49)

(a) 無序序列，初始二叉樹，97（第8/2=4個(gè)結(jié)點(diǎn)）為最后一個(gè)結(jié)點(diǎn)（49）的父結(jié)點(diǎn)。
(b) 97>=49,替換位置，接下來對(duì)n/2的上一個(gè)結(jié)點(diǎn)65進(jìn)行篩選。
(c) 13<=27且65>=13,替換65和13的位置，接下來對(duì)38進(jìn)行替換（都大于它，不需操作），對(duì)49進(jìn)行篩選。
(d) 13<=38且49>=13,替換49和13的位置，49>=27,替換49和27的位置。
(e) 最終得到一個(gè)堆，13是我們得到的最小數(shù)。

調(diào)整堆的方法（小頂堆）：

設(shè)有m 個(gè)元素的堆，輸出堆頂元素后，剩下m-1 個(gè)元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。

將根結(jié)點(diǎn)與左、右子樹中較小元素的進(jìn)行交換。

若與左子樹交換：如果左子樹堆被破壞，則重復(fù)方法(2).

若與右子樹交換，如果右子樹堆被破壞，則重復(fù)方法(2).

繼續(xù)對(duì)不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。

調(diào)整堆只需考慮被破壞的結(jié)點(diǎn)，其他的結(jié)點(diǎn)不需調(diào)整。

運(yùn)行代碼結(jié)合注釋與上面的實(shí)例步驟進(jìn)行對(duì)比思考。

package com.coder4j.main;

public class HeapSort {
    
    /** 
     * 調(diào)整為小頂堆（排序后結(jié)果為從大到小）
     * 
     * @param array是待調(diào)整的堆數(shù)組 
     * @param s是待調(diào)整的數(shù)組元素的位置
     * @param length是數(shù)組的長(zhǎng)度
     * 
     */
    public static void heapAdjustS(int[] array, int s, int length) {
        int tmp = array[s];
        int child = 2 * s + 1;// 左孩子結(jié)點(diǎn)的位置
        System.out.println("待調(diào)整結(jié)點(diǎn)為：array[" + s + "] = " + tmp);
        while (child < length) {
            // child + 1 是當(dāng)前調(diào)整結(jié)點(diǎn)的右孩子
            // 如果有右孩子且小于左孩子，使用右孩子與結(jié)點(diǎn)進(jìn)行比較，否則使用左孩子
            if (child + 1 < length && array[child] > array[child + 1]) {
                child++;
            }
            System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進(jìn)行比較");
            // 如果較小的子孩子比此結(jié)點(diǎn)小
            if (array[s] > array[child]) {
                System.out.println("子孩子比其小，交換位置");
                array[s] = array[child];// 把較小的子孩子向上移動(dòng)，替換當(dāng)前待調(diào)整結(jié)點(diǎn)
                s = child;// 待調(diào)整結(jié)點(diǎn)移動(dòng)到較小子孩子原來的位置
                array[child] = tmp;
                child = 2 * s + 1;// 繼續(xù)判斷待調(diào)整結(jié)點(diǎn)是否需要繼續(xù)調(diào)整
                
                if (child >= length) {
                    System.out.println("沒有子孩子了，調(diào)整結(jié)束");
                } else {
                    System.out.println("繼續(xù)與新的子孩子進(jìn)行比較");
                }
                // continue;
            } else {
                System.out.println("子孩子均比其大，調(diào)整結(jié)束");
                break;// 當(dāng)前待調(diào)整結(jié)點(diǎn)小于它的左右孩子，不需調(diào)整，直接退出
            }
        }
    }
    
    /** 
     * 調(diào)整為大頂堆（排序后結(jié)果為從小到大）
     * 
     * @param array是待調(diào)整的堆數(shù)組 
     * @param s是待調(diào)整的數(shù)組元素的位置
     * @param length是數(shù)組的長(zhǎng)度
     * 
     */
    public static void heapAdjustB(int[] array, int s, int length) {
        int tmp = array[s];
        int child = 2 * s + 1;// 左孩子結(jié)點(diǎn)的位置
        System.out.println("待調(diào)整結(jié)點(diǎn)為：array[" + s + "] = " + tmp);
        while (child < length) {
            // child + 1 是當(dāng)前調(diào)整結(jié)點(diǎn)的右孩子
            // 如果有右孩子且大于左孩子，使用右孩子與結(jié)點(diǎn)進(jìn)行比較，否則使用左孩子
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進(jìn)行比較");
            // 如果較大的子孩子比此結(jié)點(diǎn)大
            if (array[s] < array[child]) {
                System.out.println("子孩子比其大，交換位置");
                array[s] = array[child];// 把較大的子孩子向上移動(dòng)，替換當(dāng)前待調(diào)整結(jié)點(diǎn)
                s = child;// 待調(diào)整結(jié)點(diǎn)移動(dòng)到較大子孩子原來的位置
                array[child] = tmp;
                child = 2 * s + 1;// 繼續(xù)判斷待調(diào)整結(jié)點(diǎn)是否需要繼續(xù)調(diào)整
                
                if (child >= length) {
                    System.out.println("沒有子孩子了，調(diào)整結(jié)束");
                } else {
                    System.out.println("繼續(xù)與新的子孩子進(jìn)行比較");
                }
                // continue;
            } else {
                System.out.println("子孩子均比其小，調(diào)整結(jié)束");
                break;// 當(dāng)前待調(diào)整結(jié)點(diǎn)大于它的左右孩子，不需調(diào)整，直接退出
            }
        }
    }
      
    /**
     * 堆排序算法
     * 
     * @param array
     * @param inverse true 為倒序排列，false 為正序排列
     */
    public static void heapSort(int[] array, boolean inverse) {
        // 初始堆
        // 最后一個(gè)有孩子的結(jié)點(diǎn)位置 i = (length - 1) / 2, 以此向上調(diào)整各結(jié)點(diǎn)使其符合堆
        System.out.println("初始堆開始");
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            if (inverse) {
                heapAdjustS(array, i, array.length);
            } else {
                heapAdjustB(array, i, array.length);
            }
        }
        System.out.println("初始堆結(jié)束");
        for (int i = array.length - 1; i > 0; i--) {
            // 交換堆頂元素H[0]和堆中最后一個(gè)元素
            int tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            // 每次交換堆頂元素和堆中最后一個(gè)元素之后，都要對(duì)堆進(jìn)行調(diào)整
            if (inverse) {
                heapAdjustS(array, 0, i);
            } else {
                heapAdjustB(array, 0, i);
            }
        }
    }

    public static void main(String[] args) {
        int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 };
        heapSort(array, false);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

}

運(yùn)行結(jié)果：

初始堆開始
待調(diào)整結(jié)點(diǎn)為：array[3] = 97
將與子孩子 array[7] = 49 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[2] = 65
將與子孩子 array[5] = 13 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[1] = 38
將與子孩子 array[3] = 49 進(jìn)行比較
子孩子均比其大，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 49
將與子孩子 array[2] = 13 進(jìn)行比較
子孩子比其小，交換位置
繼續(xù)與新的子孩子進(jìn)行比較
將與子孩子 array[6] = 27 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
初始堆結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 97
將與子孩子 array[2] = 27 進(jìn)行比較
子孩子比其小，交換位置
繼續(xù)與新的子孩子進(jìn)行比較
將與子孩子 array[6] = 49 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 97
將與子孩子 array[1] = 38 進(jìn)行比較
子孩子比其小，交換位置
繼續(xù)與新的子孩子進(jìn)行比較
將與子孩子 array[3] = 49 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 65
將與子孩子 array[1] = 49 進(jìn)行比較
子孩子比其小，交換位置
繼續(xù)與新的子孩子進(jìn)行比較
將與子孩子 array[4] = 76 進(jìn)行比較
子孩子均比其大，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 76
將與子孩子 array[2] = 49 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 97
將與子孩子 array[1] = 65 進(jìn)行比較
子孩子比其小，交換位置
沒有子孩子了，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 76
將與子孩子 array[1] = 97 進(jìn)行比較
子孩子均比其大，調(diào)整結(jié)束
待調(diào)整結(jié)點(diǎn)為：array[0] = 97
97 76 65 49 49 38 27 13