【算法】排序算法之堆排序

前幾回，在前面已經對 、 、 、 、 、 做了說明分析。本回，將對堆排序

一、排序算法系列目錄說明

二、堆的相關概念

堆一般指的是二叉堆，顧名思義，二叉堆是完全二叉樹或者近似完全二叉樹

1. 堆的性質

① 是一棵完全二叉樹

② 每個節點的值都大於或等於其子節點的值，為最大堆；反之為最小堆。

2. 堆的存儲

一般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2i + 1)、(2i + 2)。

3. 堆的操作

在堆的數據結構中，堆中的最大值總是位於根節點(在優先隊列中使用堆的話堆中的最小值位於根節點)。堆中定義以下幾種操作：

① 最大堆調整（Max_Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點

② 創建最大堆（Build_Max_Heap）：將堆所有數據重新排序

③ 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

三、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

1. 基本思想

利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。

① 將待排序的序列構造成一個最大堆，此時序列的最大值為根節點

② 依次將根節點與待排序序列的最後一個元素交換

③ 再維護從根節點到該元素的前一個節點為最大堆，如此往復，最終得到一個遞增序列

2. 實現邏輯

① 先將初始的R[0…n-1]建立成最大堆，此時是無序堆，而堆頂是最大元素。

② 再將堆頂R[0]和無序區的最後一個記錄R[n-1]交換，由此得到新的無序區R[0…n-2]和有序區R[n-1]，且滿足R[0…n-2].keys

≤ R[n-1].key

④ 直到無序區只有一個元素為止。

3. 動圖演示

堆排序演示

首先，將元素進行重排，以匹配堆的條件。圖中排序過程之前簡單的繪出了堆樹的結構。

分步解析說明：

實現堆排序需要解決兩個問題：

1、如何由一個無序序列建成一個堆？

2、如何在輸出堆頂元素之後，調整剩餘元素成為一個新的堆？

假設給定一個組無序數列{100,5,3,11,6,8,7}，帶著問題，我們對其進行堆排序操作進行分步操作說明。

3.1 創建最大堆

①首先我們將數組我們將數組從上至下按順序排列，轉換成二叉樹：一個無序堆。每一個三角關係都是一個堆，上面是父節點，下面兩個分叉是子節點，兩個子節點俗稱左孩子、右孩子；

②轉換成無序堆之後，我們要努力讓這個無序堆變成最大堆(或是最小堆)，即每個堆裡都實現父節點的值都大於任何一個子節點的值。

③從最後一個堆開始，即左下角那個沒有右孩子的那個堆開始；首先對比左右孩子，由於這個堆沒有右孩子，所以只能用左孩子，左孩子的值比父節點的值小所以不需要交換。如果發生交換，要檢測子節點是否為其他堆的父節點，如果是，遞歸進行同樣的操作。

④第二次對比紅色三角形內的堆，取較大的子節點，右孩子8勝出，和父節點比較，右孩子8大於父節點3，升級做父節點，與3交換位置，3的位置沒有子節點，這個堆建成最大堆。

⑤對黃色三角形內堆進行排序，過程和上面一樣，最終是右孩子33升為父節點，被交換的右孩子下面也沒有子節點，所以直接結束對比。

⑥最頂部綠色的堆，堆頂100比左右孩子都大，所以不用交換，至此最大堆創建完成。

3.2 堆排序（最大堆調整）

①首先將堆頂元素100交換至最底部7的位置，7升至堆頂，100所在的底部位置即為有序區，有序區不參與之後的任何對比。

②在7升至頂部之後，對頂部重新做最大堆調整，左孩子33代替7的位置。

③在7被交換下來後，下面還有子節點，所以需要繼續與子節點對比，左孩子11比7大，所以11與7交換位置，交換位置後7下面為有序區，不參與對比，所以本輪結束，無序區再次形成一個最大堆。

④將最大堆堆頂33交換至堆末尾，擴大有序區；

⑤不斷建立最大堆，並且擴大有序區，最終全部有序。

4. 複雜度分析

平均時間複雜度：O(nlogn)

最佳時間複雜度：O(nlogn)

最差時間複雜度：O(nlogn)

穩定性：不穩定

堆排序其實也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R[1…n]中選擇最大記錄，需比較n-1次，然後從R[1…n-2]中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經在前面的n-1次比較中已經做過，而樹形選擇排序恰好利用樹形的特點保存了部分前面的比較結果，因此可以減少比較次數。對於n個關鍵字序列，最壞情況下每個節點需比較log2(n)次，因此其最壞情況下時間複雜度為nlogn。堆排序為不穩定排序，不適合記錄較少的排序。

5. 代碼實現

C版本：

<code>#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}
void max_heapify(int arr[], int start, int end) {
    //建立父節點指標和子節點指標 

    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { //否則交換父子內容再繼續子節點和孫節點比較
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len) {
    int i;
    //初始化，i從最後一個父節點開始調整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\\n");
    return 0;
}/<stdlib.h>/<stdio.h>/<code>

C++版本：

<code>#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
    //建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { //否則交換父子內容再繼續子節點和孫節點比較
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len) {
    //初始化，i從最後一個父節點開始調整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl; 

    return 0;
}/<algorithm>/<iostream>/<code>

Java版本：

<code>import java.util.Arrays;
public class HeapSort {

    private int[] arr;

    public HeapSort(int[] arr){
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共兩步。
     */
    public void sort(){
        /*
         *  第一步：將數組堆化
         *  beginIndex = 第一個非葉子節點。
         *  從第一個非葉子節點開始即可。無需從最後一個葉子節點開始。
         *  葉子節點可以看作已符合堆要求的節點，根節點就是它自己且自己以下值為最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1;
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }

        /*
         * 第二步：對堆化數據排序
         * 每次都是移出最頂層的根節點A[0]，與最尾部節點位置調換，同時遍歷長度 - 1。
         * 然後從新整理被換到根節點的末尾元素，使其符合堆的特性。 

         * 直至未排序的堆長度為 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 調整索引為 index 處的數據，使其符合堆的特性。
     *
     * @param index 需要堆化處理的數據的索引
     * @param len 未排序的堆（數組）的長度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子節點索引
        int ri = li + 1;           // 右子節點索引
        int cMax = li;             // 子節點值最大索引，默認左子節點。

        if(li > len) return;       // 左子節點索引超出計算範圍，直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判斷左右子節點，哪個較大。
            cMax = ri;
        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父節點被子節點調換，
            maxHeapify(cMax, len);  // 則需要繼續判斷換下後的父節點是否符合堆的特性。
        }
    }

    /**
     * 測試用例 

     *
     * 輸出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};        
        new HeapSort(arr).sort();        
        System.out.println(Arrays.toString(arr));
    }/<code>

四、總結

堆是一種很好做調整的結構，在算法題裡面使用頻度很高。常用於想知道最大值或最小值的情況，比如優先級隊列，作業調度等場景。

堆排序相看似比較複雜（建堆的過程，堆調整的過程，堆排序等等），需要好好推敲揣摩理清思路。堆排序操作過程中其運行時間主要耗費在建初始堆和調整建新堆時進行的反覆“篩選”上。

下一篇預告：計數排序（Counting Sort）。欲知詳情，且聽下回分解。

PS: 更多精選內容資源分享，歡迎關注微信公眾號：『 developer1024 』

閱讀更多 休閒遊戲人 的文章

關鍵字: 數據結構 設計 算法