堆

堆排序需要用到二叉堆，在開始之前，我們先來了解一下什么是二叉堆。

當(dāng)二叉樹滿足滿足如下條件時，我們說這個二叉樹是堆有序的：

1. 每一個父結(jié)點(diǎn)的值都比它的子結(jié)點(diǎn)大（稱為大頂堆）或小（稱為小頂堆）
2. 子結(jié)點(diǎn)的大小與其左右位置無關(guān)

堆有序的二叉樹，也可稱為二叉堆。二叉堆是最常見的堆結(jié)構(gòu)，因此也常將二叉堆直接稱為堆，可以采用如下兩種方式來表示二叉堆

1. 使用指針，二叉樹的每個結(jié)點(diǎn)需存儲三個指針，分別指向其父結(jié)點(diǎn)和兩個子結(jié)點(diǎn)
2. 使用數(shù)組，對二叉樹做層序遍歷，按層級順序放入數(shù)組中，根結(jié)點(diǎn)在數(shù)組索引0的位置存放，其子結(jié)點(diǎn)分別在索引1和2的位置，1和2個子結(jié)點(diǎn)分別在位置3、4和5、6中存放，以此類推

就排序來講，其所需處理的數(shù)據(jù)較為連續(xù)，沒有空隙，可用完全二叉樹來表示。對于完全二叉樹，采用數(shù)組的表示方法也更方便些，下圖展示了采用數(shù)組實(shí)現(xiàn)的兩個二叉堆。

二叉堆

對于數(shù)組實(shí)現(xiàn)的二叉堆，索引為k的結(jié)點(diǎn)的父結(jié)點(diǎn)的索引為(k-1)/2，它的子結(jié)點(diǎn)的索引分別為2k+1和2k+2。

堆有序化

以大頂堆為例，有序化的過程中我們會遇到兩種情況

1. 在堆底加入一個較大元素時，我們需要由下至上恢復(fù)堆的順序
2. 當(dāng)將根結(jié)點(diǎn)替換為一個較小元素時，我們需要由上到下恢復(fù)堆的順序

由下至上的堆有序化（上?。?/h4>

如果堆的有序狀態(tài)因?yàn)槟硞€結(jié)點(diǎn)變的比它的父結(jié)點(diǎn)更大而被打破，就需要通過將它與它的父結(jié)點(diǎn)交換來恢復(fù)堆有序。交換后，這個結(jié)點(diǎn)比它的兩個子結(jié)點(diǎn)都大，但這個結(jié)點(diǎn)仍然可能比它現(xiàn)在的父結(jié)點(diǎn)更大。我們可以一遍遍的用同樣的方式來將其向上移動，直到遇到一個比它更大的父結(jié)點(diǎn)或到達(dá)了堆的根結(jié)點(diǎn)，如下圖所示。

由下至上的堆有序化（上浮）

上浮操作對應(yīng)的代碼如下

private void swim(Integer arr[], int k) {
    while(k > 0 && arr[(k - 1) / 2] < arr[k]) { //若k>0且索引為k的結(jié)點(diǎn)大于其父結(jié)點(diǎn)時，將該結(jié)點(diǎn)與其父結(jié)點(diǎn)交換
        swap(arr, k, (k - 1) / 2);
        k = (k - 1) / 2;
    }
}

由上至下的堆有序化（下沉）

如果堆的有序狀態(tài)因?yàn)槟硞€結(jié)點(diǎn)變的比它的某個子結(jié)點(diǎn)更小而被打破，就需要通過將它和它的子結(jié)點(diǎn)中較大者交換位置來恢復(fù)堆有序。交換可能會在子結(jié)點(diǎn)處繼續(xù)打破堆的有序狀態(tài)，此時可以采用相同的方式，將結(jié)點(diǎn)向下移動直到它的子結(jié)點(diǎn)都比它小或是到達(dá)了堆的底部，如下圖所示。

由上至下的堆有序化（下沉）

下沉操作對應(yīng)的代碼如下

private void sink(Integer arr[], int k) {
    while(2 * k + 1 <= arr.length - 1) {//若k存在子結(jié)點(diǎn)，則進(jìn)入循環(huán)
        int j = 2 * k + 1; //獲取k的第一個子結(jié)點(diǎn)
        if (j < arr.length - 1 && arr[j] < arr[j + 1]) {//若存在兩個子結(jié)點(diǎn)，則找到其中較大的子結(jié)點(diǎn)
            j++;
        }
        if (arr[j] > arr[k]) {//若k的較大子結(jié)點(diǎn)比k大，則交換它們的位置
            swap(arr, j, k);
            k = j;
        }
    }
}

堆排序

在介紹完堆的數(shù)據(jù)結(jié)構(gòu)和操作方式后，我們來看堆排序是如何進(jìn)行的。

堆的構(gòu)造

1. 將原數(shù)組看做堆的話，則最后一個分支結(jié)點(diǎn)（含有子結(jié)點(diǎn)的結(jié)點(diǎn)）在原數(shù)組中的索引為 (n-1)/2 -1
2. 從(n-1)/2-1向前依次執(zhí)行下沉操作，從而得到堆有序的數(shù)組

堆初始化

堆的排序

1. 取出堆的根結(jié)點(diǎn)，與數(shù)組最后一個元素交換。交換后堆有序狀態(tài)可能會被打破，需要在新的根結(jié)點(diǎn)進(jìn)行下沉操作，使其恢復(fù)為堆有序狀態(tài)。此時數(shù)組中最大(大頂堆)/最小(小頂堆)的值存放在數(shù)組末位，除它以外的最 大/小 值位于堆頂。
2. 從數(shù)組中排除最后一個元素，重復(fù)步驟2，直到數(shù)組中的元素全部排除時，完成排序

堆排序

public static void heapSort(Integer arr[]) {
    int n = arr.length;
    //堆的構(gòu)造,對每一個含有孩子的結(jié)點(diǎn)做下沉操作,得到大頂堆
    for (int i = (n-1) /2 -1; i >= 0; i--) {
        heapSink(arr, i, n);
    }
    printArr(arr, "大頂堆");
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapSink(arr, 0, i);
    }
    printArr(arr, "堆排序");

}

public static void heapSink(Integer arr[], int i, int length) {
    while(2 * k + 1 <= length - 1) {//若k存在子結(jié)點(diǎn)，則進(jìn)入循環(huán)
        int j = 2 * k + 1; //獲取k的第一個子結(jié)點(diǎn)
        if (j < length - 1 && arr[j] < arr[j + 1]) {//若存在兩個子結(jié)點(diǎn)，則找到其中較大的子結(jié)點(diǎn)
            j++;
        }
        if (arr[j] > arr[k]) {//若k的較大子結(jié)點(diǎn)比k大，則交換它們的位置
            swap(arr, j, k);
            k = j;
        }
    }
}

堆排序動態(tài)圖

堆排序動態(tài)圖

小結(jié)

堆排序算法也是一種選擇排序算法，整體由堆的構(gòu)建、堆的交換與下沉兩個步驟組成。其中堆的構(gòu)建需要比較(n-1)/2-1次下沉，每次下沉至多交換一次，時間復(fù)雜度為O(n)；堆的交換與下沉中需交換n次，下沉依次需要執(zhí)行\log_2(n-1),log_2(n-2)...1次交換，近似為Nlog_2N。因此堆排序的時間復(fù)雜度為O(N\log_2N)