一文讀懂堆排序

（點擊上方公眾號，可快速關注）

轉自：劉毅

https://61mon.com/index.php/archives/202/

好文投稿， 請點擊 → 這裡了解詳情

堆排序是利用堆的性質進行的一種選擇排序。下面先討論一下堆。

堆實際上是一棵完全二叉樹，其滿足性質：任何一結點大於等於或者小於等於其左右子樹結點。

堆分為大頂堆和小頂堆，滿足 「任何一結點大於等於其左右子樹結點」 的稱為大頂堆，滿足 「任何一結點小於等於其左右子樹結點」 的稱為小頂堆。

由上述性質可知：大頂堆的堆頂肯定是最大的，小頂堆的堆頂是最小的。

下面舉個例子（資源來自堆排序 - 海子）來說明堆排序的過程（以升序為例）：

給定整型數組：{16, 7, 3, 20, 17, 8}，根據該數組 「構建」 完全二叉樹（並不是真的寫代碼去構建，只是把數組看成完全二叉樹去操作）。

程序從最後一個非葉子結點開始，即 3。判斷其左右孩子：8，8 比 3 大，把 8 調整上去。

3 結點下無孩子，判斷結束。

繼續往前一步，至 7 結點，判斷其左右孩子：20 和 17，20 是最大的，將其調整上去。

7 結點下無孩子，判斷結束。

繼續往前一步，至 16 結點，判斷其左右孩子：20 和 8，20 是最大的，將其調整上去。

判斷 16 結點下左右孩子：7 和 17，17 是最大的，將其調整上去。

16 結點下無孩子，判斷結束。

遍歷已至頭部，結束。

至此數組已經滿足大頂堆的性質，接下來的操作就很簡單了。

看完上面所述的流程你至少有兩個疑問：

1、如何確定最後一個非葉子結點？

其實這是有一個公式的，設二叉樹結點總數為 n，則最後一個非葉子結點是第 ⌊n2⌋ 個。

2、數組當中如何確定當前結點的左右孩子位置？

設當前結點下標是 i，則其左孩子的下標是 2i，右孩子的下標是 2i+1。請注意：這是建立在數組下標從 1 開始的情況。若數組下標從 0 開始，則其左右孩子下標還各需多加一個 1。

以下代碼默認數組下標從 1 開始，請讀者注意。

/* 已知 array[left]...array[right] 的值除 array[left] 之外均滿足堆的定義，

本函數調整 array[left]，使 array[left]...array[right] 成一個大頂堆 */

void HeapAdjust(int array[], int left, int right)

{

    int index = left;

  

    for (int i = left * 2; i <= right; i = i * 2)

    {

        if (i < right && array[i] < array[i + 1])  // 找到孩子中較大者

            i++;

        if (array[index] > array[i])

            return;

        swap(array[index], array[i]);

        index = i;

    }

}

void HeapSort(int array[], int left, int right)

{

    int len = right - left + 1;

  

    for (int i = len / 2; i >= left; i--)  // 把數組調整成大頂堆

        HeapAdjust(array, i, right);

  

    for (int i = right; i > left; i--)     // 排序

    {

        swap(array[left], array[i]);

        HeapAdjust(array, left, i - 1);

    }

}

時間複雜度為 O(nlogn)，證明如下。

首先計算建堆的時間，也就是下面的代碼，

for (int i = len / 2; i >= left; i--)  // 把數組調整成大頂堆

    HeapAdjust(array, i, right);

接下來就是排序的時間，即下面的代碼：

for (int i = right; i > left; i--)  // 排序

{

    swap(array[left], array[i]);

    HeapAdjust(array, left, i - 1);

}

HeapAdjust( ) 耗時 logn，共 n 次，故排序時間為 O(nlogn)。

綜上所述，堆排序時間複雜度為 T(n)=O(n)+O(nlogn)=O(nlogn)。

覺得本文有幫助？請分享給更多人

關注「算法愛好者」，修煉編程內功

淘口令：複製以下紅色內容，再打開手淘即可購買

範品社，使用￥極客T恤￥搶先預覽（長按複製整段文案，打開手機淘寶即可進入活動內容）