堆排序的詳細(xì)制度一、堆排序概述

堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的比較排序算法，具有時間復(fù)雜度為O(nlogn)的特性。它通過構(gòu)建最大堆或最小堆來實(shí)現(xiàn)排序，主要分為兩個核心步驟：構(gòu)建堆和堆調(diào)整。堆排序算法具有空間復(fù)雜度為O(1)，屬于原地排序算法。

（一）堆的定義與性質(zhì)

1.堆是一種完全二叉樹結(jié)構(gòu)，分為最大堆和最小堆兩種類型。

-最大堆：父節(jié)點(diǎn)的值始終大于或等于子節(jié)點(diǎn)的值。

-最小堆：父節(jié)點(diǎn)的值始終小于或等于子節(jié)點(diǎn)的值。

2.堆的存儲方式通常采用數(shù)組，其中節(jié)點(diǎn)i的左子節(jié)點(diǎn)為2i+1，右子節(jié)點(diǎn)為2i+2，父節(jié)點(diǎn)為(i-1)/2（向下取整）。

（二）堆排序的基本步驟

1.構(gòu)建初始堆：將待排序數(shù)組轉(zhuǎn)化為最大堆或最小堆。

2.堆調(diào)整：通過交換堆頂元素與當(dāng)前末尾元素，逐步減少堆的大小，并重新調(diào)整堆。

3.最終排序：經(jīng)過多輪堆調(diào)整后，數(shù)組將按升序或降序排列。

二、堆排序的實(shí)現(xiàn)細(xì)節(jié)

（一）構(gòu)建最大堆

1.從最后一個非葉子節(jié)點(diǎn)開始向前遍歷，對每個節(jié)點(diǎn)執(zhí)行堆調(diào)整。

-非葉子節(jié)點(diǎn)的索引范圍：n/2-1到0（n為數(shù)組長度）。

2.堆調(diào)整過程：

-初始化當(dāng)前節(jié)點(diǎn)為i，其左右子節(jié)點(diǎn)分別為2i+1和2i+2。

-比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)的值，找出最大值所在節(jié)點(diǎn)。

-若最大值不在當(dāng)前節(jié)點(diǎn)，則交換位置，并繼續(xù)對子樹進(jìn)行堆調(diào)整。

（二）堆調(diào)整算法

1.輸入：當(dāng)前節(jié)點(diǎn)索引i，堆的大小n。

2.步驟：

(1)初始化最大索引為i。

(2)比較當(dāng)前節(jié)點(diǎn)與左子節(jié)點(diǎn)（2i+1），若左子節(jié)點(diǎn)更大，則更新最大索引為左子節(jié)點(diǎn)索引。

(3)比較當(dāng)前節(jié)點(diǎn)與右子節(jié)點(diǎn)（2i+2），若右子節(jié)點(diǎn)更大，則更新最大索引為右子節(jié)點(diǎn)索引。

(4)若最大索引不為i，則交換i與最大索引處的值，并遞歸對子樹進(jìn)行堆調(diào)整。

（三）堆排序完整流程

1.構(gòu)建初始最大堆：

-從n/2-1開始，逐個向前遍歷并調(diào)整節(jié)點(diǎn)，直至到達(dá)根節(jié)點(diǎn)（索引0）。

2.排序過程：

(1)交換堆頂元素（當(dāng)前最大值）與數(shù)組末尾元素。

(2)減少堆的大?。╪減1），并重新調(diào)整根節(jié)點(diǎn)為最大值。

(3)重復(fù)步驟(1)和(2)，直至堆的大小為1。

三、堆排序的優(yōu)缺點(diǎn)

（一）優(yōu)點(diǎn)

1.時間復(fù)雜度穩(wěn)定：無論輸入數(shù)據(jù)如何，堆排序的時間復(fù)雜始終為O(nlogn)。

2.空間復(fù)雜度低：僅使用常數(shù)級額外空間，屬于原地排序算法。

3.適合大規(guī)模數(shù)據(jù)：對于內(nèi)存受限場景，堆排序表現(xiàn)優(yōu)于某些需要額外存儲的排序算法。

（二）缺點(diǎn)

1.實(shí)現(xiàn)復(fù)雜度較高：堆調(diào)整過程涉及遞歸或循環(huán)，代碼邏輯相對復(fù)雜。

2.非穩(wěn)定排序：相同值的元素在排序后相對順序可能改變。

3.相比快速排序：在平均情況下性能略遜，但更穩(wěn)定。

四、示例說明

以數(shù)組[4,10,3,5,1]為例，展示堆排序過程：

（一）構(gòu)建初始最大堆

1.非葉子節(jié)點(diǎn)索引：2（值為10）和1（值為4）。

2.調(diào)整節(jié)點(diǎn)2（10）：左右子節(jié)點(diǎn)分別為4和3，無需調(diào)整。

3.調(diào)整節(jié)點(diǎn)1（4）：右子節(jié)點(diǎn)（值為5）大于當(dāng)前節(jié)點(diǎn)，交換后數(shù)組變?yōu)閇4,5,3,10,1]。

4.最終堆結(jié)構(gòu)：[10,5,3,4,1]。

（二）排序過程

1.交換10與1，數(shù)組變?yōu)閇1,5,3,4,10]。

2.減少堆大小為4，調(diào)整根節(jié)點(diǎn)5：

-比較節(jié)點(diǎn)5與子節(jié)點(diǎn)4和3，無需調(diào)整。

-數(shù)組變?yōu)閇1,4,3,5,10]。

3.交換4與5，數(shù)組變?yōu)閇1,3,4,5,10]。

4.減少堆大小為3，調(diào)整根節(jié)點(diǎn)3：

-比較節(jié)點(diǎn)3與子節(jié)點(diǎn)4和1，無需調(diào)整。

-數(shù)組保持[1,3,4,5,10]。

5.交換3與1，數(shù)組變?yōu)閇1,3,4,5,10]。

6.減少堆大小為2，調(diào)整根節(jié)點(diǎn)3：

-比較節(jié)點(diǎn)3與子節(jié)點(diǎn)4和1，無需調(diào)整。

-數(shù)組保持[1,3,4,5,10]。

最終排序結(jié)果：[1,3,4,5,10]。

一、堆排序概述

堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的比較排序算法，具有時間復(fù)雜度為O(nlogn)的特性。它通過構(gòu)建最大堆或最小堆來實(shí)現(xiàn)排序，主要分為兩個核心步驟：構(gòu)建堆和堆調(diào)整。堆排序算法具有空間復(fù)雜度為O(1)，屬于原地排序算法。

（一）堆的定義與性質(zhì)

1.堆是一種完全二叉樹結(jié)構(gòu)，分為最大堆和最小堆兩種類型。

-最大堆：父節(jié)點(diǎn)的值始終大于或等于子節(jié)點(diǎn)的值。這種堆結(jié)構(gòu)確保了堆頂元素是整個堆中的最大值。

-最小堆：父節(jié)點(diǎn)的值始終小于或等于子節(jié)點(diǎn)的值。這種堆結(jié)構(gòu)確保了堆頂元素是整個堆中的最小值。

2.堆的存儲方式通常采用數(shù)組，這種存儲方式具有空間效率高、訪問速度快的特點(diǎn)。在數(shù)組中，對于任意節(jié)點(diǎn)i（從0開始索引）：

-其左子節(jié)點(diǎn)的索引為`2i+1`

-其右子節(jié)點(diǎn)的索引為`2i+2`

-其父節(jié)點(diǎn)的索引為`(i-1)/2`（向下取整）

這種索引關(guān)系使得我們可以通過簡單的數(shù)學(xué)運(yùn)算直接訪問節(jié)點(diǎn)的子節(jié)點(diǎn)和父節(jié)點(diǎn)，無需指針或鏈表結(jié)構(gòu)，這也是堆排序能夠?qū)崿F(xiàn)原地排序（空間復(fù)雜度O(1)）的關(guān)鍵原因之一。

（二）堆排序的基本步驟

堆排序算法通過兩個主要階段對輸入數(shù)組進(jìn)行排序：

1.構(gòu)建初始堆：此階段的目標(biāo)是將一個無序的輸入數(shù)組轉(zhuǎn)換成一個滿足堆性質(zhì)的完全二叉樹（通常是最大堆）。這一步是后續(xù)排序操作的基礎(chǔ)。

2.堆調(diào)整與排序：在初始堆構(gòu)建完成后，通過反復(fù)“移除”堆頂元素（在最大堆中是最大值，在最小堆中是最小值）并“調(diào)整”剩余元素以維持堆性質(zhì)，逐步將最大（或最?。┰亍懊芭荨钡綌?shù)組的末尾。這個過程會重復(fù)進(jìn)行，直到堆的大小減至1，此時數(shù)組已經(jīng)是有序的。

3.最終輸出：經(jīng)過上述過程，數(shù)組會按照指定順序（升序或降序，取決于使用最大堆還是最小堆）排列。通常，如果使用最大堆并按升序排序，最后得到的數(shù)組就是升序排列的。

二、堆排序的實(shí)現(xiàn)細(xì)節(jié)

（一）構(gòu)建最大堆

構(gòu)建最大堆是堆排序的第一步，其目的是確保從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑上，節(jié)點(diǎn)的值都是遞減的（即父節(jié)點(diǎn)>=子節(jié)點(diǎn)）。這一步通常采用自底向上的方式實(shí)現(xiàn)。

1.確定非葉子節(jié)點(diǎn)的范圍：在一個有n個元素的數(shù)組中，非葉子節(jié)點(diǎn)是從`n/2-1`到`0`的所有索引（假設(shè)數(shù)組索引從0開始）。只有這些節(jié)點(diǎn)可能有子節(jié)點(diǎn)，因此只需要對這些節(jié)點(diǎn)進(jìn)行堆調(diào)整。

-理由：索引大于或等于`n/2`的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)（在完全二叉樹中，最后一個非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)索引至少為`2(n/2)=n`）。

2.對每個非葉子節(jié)點(diǎn)執(zhí)行堆調(diào)整：

-從最后一個非葉子節(jié)點(diǎn)開始，逐個向前遍歷至根節(jié)點(diǎn)（索引0）。

-對于當(dāng)前節(jié)點(diǎn)i，首先假設(shè)其本身就是最大值。

-比較當(dāng)前節(jié)點(diǎn)i與其兩個子節(jié)點(diǎn)（左子節(jié)點(diǎn)`2i+1`和右子節(jié)點(diǎn)`2i+2`，如果存在）的值。

-找出三個節(jié)點(diǎn)（i,`2i+1`,`2i+2`）中的最大值，并記錄其索引（記為`largest`）。

-如果`largest`不等于i（即當(dāng)前節(jié)點(diǎn)不是最大值），則將當(dāng)前節(jié)點(diǎn)i的值與索引為`largest`的節(jié)點(diǎn)的值進(jìn)行交換。

-交換后，由于被交換到位置i的節(jié)點(diǎn)的原始子樹可能已經(jīng)破壞了堆的性質(zhì)，因此需要以`largest`的位置為根，對其子樹進(jìn)行遞歸的堆調(diào)整。

-這個過程會一直持續(xù)，直到當(dāng)前節(jié)點(diǎn)i的子樹滿足堆性質(zhì)，或者當(dāng)前節(jié)點(diǎn)成為葉子節(jié)點(diǎn)。

（二）堆調(diào)整算法（詳細(xì)步驟）

堆調(diào)整是維護(hù)堆性質(zhì)的核心操作。給定一個節(jié)點(diǎn)索引`i`和當(dāng)前堆的大小`n`，堆調(diào)整的目標(biāo)是確保以節(jié)點(diǎn)`i`為根的子樹滿足最大堆性質(zhì)。

1.輸入?yún)?shù)：

-`i`:當(dāng)前需要檢查并可能調(diào)整的節(jié)點(diǎn)在堆中的索引。

-`n`:當(dāng)前堆中有效的元素數(shù)量（即堆的實(shí)際大小，用于防止訪問到數(shù)組邊界之外的元素）。

2.初始化最大索引：設(shè)定`largest=i`，表示當(dāng)前節(jié)點(diǎn)`i`是候選的最大值。

3.檢查左子節(jié)點(diǎn)：

-計算左子節(jié)點(diǎn)的索引：`left=2i+1`。

-如果`left`小于`n`（即左子節(jié)點(diǎn)存在），并且左子節(jié)點(diǎn)的值`array[left]`大于當(dāng)前記錄的最大值`array[largest]`，則更新`largest=left`。

4.檢查右子節(jié)點(diǎn)：

-計算右子節(jié)點(diǎn)的索引：`right=2i+2`。

-如果`right`小于`n`（即右子節(jié)點(diǎn)存在），并且右子節(jié)點(diǎn)的值`array[right]`大于當(dāng)前記錄的最大值`array[largest]`，則更新`largest=right`。

5.比較最大索引與當(dāng)前節(jié)點(diǎn)：

-經(jīng)過步驟3和4后，`largest`存儲了`i`、`2i+1`、`2i+2`中最大值的索引。

-如果`largest`不等于`i`（即當(dāng)前節(jié)點(diǎn)不是三個比較節(jié)點(diǎn)中的最大值），則說明當(dāng)前節(jié)點(diǎn)`i`不滿足最大堆性質(zhì)。

-將當(dāng)前節(jié)點(diǎn)`i`的值與索引為`largest`的節(jié)點(diǎn)的值進(jìn)行交換：`swap(array[i],array[largest])`。

-交換后，原位于`largest`位置的節(jié)點(diǎn)移動到了位置`i`。由于這個新節(jié)點(diǎn)`largest`可能位于一個非葉子節(jié)點(diǎn)上，其子樹可能已經(jīng)破壞了堆的性質(zhì)，因此必須對新的`largest`位置（即原`i`位置）進(jìn)行遞歸的堆調(diào)整。

-遞歸調(diào)用堆調(diào)整函數(shù)：`heapify(array,n,largest)`。

-如果`largest`等于`i`，則說明當(dāng)前節(jié)點(diǎn)及其子樹已經(jīng)滿足最大堆性質(zhì)，無需進(jìn)一步操作，遞歸結(jié)束。

6.終止條件：遞歸的終止條件是`largest`索引對應(yīng)的節(jié)點(diǎn)不再有子節(jié)點(diǎn)（即`largest>=n/2`），或者交換后新的`largest`節(jié)點(diǎn)已經(jīng)滿足堆性質(zhì)。

（三）堆排序完整流程（分步驟詳解）

堆排序算法將排序過程清晰地劃分為以下步驟：

1.構(gòu)建初始最大堆：

-確定數(shù)組的長度`n`。

-計算最后一個非葉子節(jié)點(diǎn)的索引：`end=n/2-1`。

-從索引`end`開始，逐個向前遍歷到索引`0`，對每個索引`i`執(zhí)行堆調(diào)整操作。

-調(diào)用`heapify(array,n,i)`。

-完成這一步后，整個數(shù)組構(gòu)成一個最大堆，堆頂元素（索引`0`）是數(shù)組中的最大值。

2.排序階段：

-初始化堆的大小`n`為數(shù)組的實(shí)際長度。

-進(jìn)入一個循環(huán)，持續(xù)執(zhí)行直到堆的大小`n`減至`1`。

-循環(huán)體內(nèi)的主要操作：

(1)交換堆頂與末尾元素：

-交換索引`0`（堆頂）的元素與索引`n-1`（當(dāng)前堆的最后一個元素）的元素。

-這將最大元素“移出”堆結(jié)構(gòu)，放置到數(shù)組的末尾。

(2)減少堆的大?。?/p>

-將堆的大小`n`減`1`，因為最后一個元素已經(jīng)確定是當(dāng)前剩余元素中的最大值，不再屬于堆的一部分。

(3)調(diào)整新堆頂：

-對新的堆頂元素（原數(shù)組末尾被移出的元素現(xiàn)在位于索引`0`）執(zhí)行堆調(diào)整操作。

-調(diào)用`heapify(array,n,0)`。

-這一步是為了將新的最大值“冒泡”到堆頂。

-重復(fù)步驟(1)到(3)，直到堆的大小為`1`。

3.輸出結(jié)果：

-當(dāng)堆的大小減至`1`時，循環(huán)結(jié)束。此時，數(shù)組的前`n-1`個元素已經(jīng)是有序的（假設(shè)使用最大堆并按升序排序，則從后向前有序）。

-數(shù)組的最后一個元素是整個數(shù)組中的最大值。

-通常，為了得到完整的升序數(shù)組，可以在排序結(jié)束后對數(shù)組進(jìn)行一次反轉(zhuǎn)，或者直接從數(shù)組的第二個元素開始遍歷（索引`1`到`n-1`）即可獲得升序結(jié)果。

三、堆排序的優(yōu)缺點(diǎn)

（一）優(yōu)點(diǎn)

1.時間復(fù)雜度穩(wěn)定：堆排序的最壞、平均和最好時間復(fù)雜度均為O(nlogn)。這一特性使得堆排序在處理大規(guī)模數(shù)據(jù)時，性能表現(xiàn)具有可預(yù)測性，不像快速排序那樣在最壞情況下退化到O(n^2)。

2.空間復(fù)雜度低：堆排序是原地排序算法，它只需要常數(shù)級的額外空間（通常用于堆調(diào)整過程中的交換操作），空間復(fù)雜度為O(1)。這使得它在內(nèi)存資源有限的環(huán)境下非常適用。

3.適合大規(guī)模數(shù)據(jù)：由于其O(nlogn)的時間復(fù)雜度，并且是原地排序，堆排序適合處理數(shù)據(jù)量巨大且內(nèi)存受限的場景，例如在外部排序中作為核心排序步驟。

4.非比較依賴：堆排序本質(zhì)上是比較排序，不依賴于特定數(shù)據(jù)類型的大小比較，只要比較操作定義良好，就可以應(yīng)用于各種可排序的數(shù)據(jù)。

（二）缺點(diǎn)

1.實(shí)現(xiàn)復(fù)雜度較高：堆排序的代碼實(shí)現(xiàn)比冒泡排序、選擇排序或插入排序更復(fù)雜，特別是堆調(diào)整的邏輯涉及遞歸或循環(huán)，容易出錯。理解堆的結(jié)構(gòu)和堆調(diào)整的過程對于正確實(shí)現(xiàn)堆排序是一個挑戰(zhàn)。

2.非穩(wěn)定排序：堆排序是一種不穩(wěn)定排序算法。這意味著對于兩個具有相同值的元素，排序后它們的相對順序可能會與排序前不同。例如，在最大堆中，兩個值相同的元素A和B，如果A在B之前，但在構(gòu)建堆和后續(xù)調(diào)整過程中，A和B的位置可能會交換。

3.緩存局部性可能較差：與快速排序等訪問模式更規(guī)律（如二分法劃分）的算法相比，堆排序在訪問數(shù)組元素時可能具有更差的局部性，因為堆調(diào)整過程可能訪問數(shù)組的遠(yuǎn)端元素，導(dǎo)致緩存未命中率較高，從而影響實(shí)際運(yùn)行速度。不過，對于某些特定硬件，這種影響可能不顯著。

四、示例說明（以最大堆構(gòu)建和排序為例）

我們以一個具體的無序數(shù)組`[4,10,3,5,1]`為例，詳細(xì)演示堆排序的每一步操作。假設(shè)數(shù)組索引從`0`開始。

（一）構(gòu)建初始最大堆

假設(shè)數(shù)組為`array=[4,10,3,5,1]`，長度`n=5`。

1.計算最后一個非葉子節(jié)點(diǎn)的索引：`end=n/2-1=5/2-1=2`。因此，需要檢查索引`2`和`1`的節(jié)點(diǎn)。

2.檢查節(jié)點(diǎn)`i=2`（值為`3`）：

-左子節(jié)點(diǎn)索引`left=22+1=5`。`left`等于`n`，表示沒有左子節(jié)點(diǎn)。

-右子節(jié)點(diǎn)索引`right=22+2=6`。`right`大于`n`，表示沒有右子節(jié)點(diǎn)。

-由于沒有子節(jié)點(diǎn)，節(jié)點(diǎn)`2`已經(jīng)滿足最大堆性質(zhì)，無需調(diào)整。

3.檢查節(jié)點(diǎn)`i=1`（值為`10`）：

-左子節(jié)點(diǎn)索引`left=21+1=3`。值為`5`。

-右子節(jié)點(diǎn)索引`right=21+2=4`。值為`1`。

-比較`i=1`（10），`left=3`（5），`right=4`（1），最大值為`10`，位于`i=1`。

-最大索引`largest=1`，不等于`i=1`，無需交換。

-節(jié)點(diǎn)`i=1`已經(jīng)滿足最大堆性質(zhì)。

4.檢查節(jié)點(diǎn)`i=0`（值為`4`）：

-左子節(jié)點(diǎn)索引`left=20+1=1`。值為`10`。

-右子節(jié)點(diǎn)索引`right=20+2=2`。值為`3`。

-比較`i=0`（4），`left=1`（10），`right=2`（3），最大值為`10`，位于`left=1`。

-最大索引`largest=1`，不等于`i=0`。

-交換`array[0]`和`array[1]`：交換`4`和`10`。

-交換后數(shù)組：`[10,4,3,5,1]`。

-交換完成后，節(jié)點(diǎn)`0`（現(xiàn)在值為`10`）需要檢查其子節(jié)點(diǎn)（`left=1`（4），`right=2`（3））。

-比較`i=0`（10），`left=1`（4），`right=2`（3），最大值仍為`10`，位于`i=0`。

-節(jié)點(diǎn)`i=0`滿足最大堆性質(zhì)。

5.最終構(gòu)建的最大堆數(shù)組：`[10,4,3,5,1]`。

-驗證：根節(jié)點(diǎn)`10`>=左子節(jié)點(diǎn)`4`，`10`>=右子節(jié)點(diǎn)`3`。父節(jié)點(diǎn)`4`>=左子節(jié)點(diǎn)`5`，父節(jié)點(diǎn)`4`>=右子節(jié)點(diǎn)`1`。父節(jié)點(diǎn)`3`>=左子節(jié)點(diǎn)`5`，父節(jié)點(diǎn)`3`>=右子節(jié)點(diǎn)`1`。堆性質(zhì)滿足。

（二）堆調(diào)整與排序過程

排序階段開始，初始堆大小`n=5`。

1.第一輪：

-交換堆頂（索引`0`，值為`10`）與末尾（索引`n-1=4`，值為`1`）：

-交換后數(shù)組：`[1,4,3,5,10]`。

-減少堆的大?。篳n=4`。

-調(diào)整新堆頂（索引`0`，值為`1`）：

-`largest=0`。

-`left=1`，`array[1]=4`。`largest=max(0,1)=1`。

-`right=2`，`array[2]=3`。`largest=max(1,2)=1`。

-`largest=1`!=`i=0`。交換`array[0]`和`array[1]`：`[4,1,3,5,10]`。

-遞歸調(diào)整`largest=1`（值為`1`）：

-`left=3`，`array[3]=5`。`largest=max(1,3)=3`。

-`right=4`，`array[4]=10`。`largest=max(3,4)=4`。

-`largest=4`!=`i=1`。交換`array[1]`和`array[4]`：`[4,10,3,5,1]`。

-遞歸調(diào)整`largest=4`（值為`1`）：

-`left=7`，超出范圍`n=4`。終止。

-第一輪結(jié)束，堆結(jié)構(gòu)為`[4,10,3,5,1]`，但末尾元素已為`1`。

2.第二輪：

-交換堆頂（索引`0`，值為`4`）與末尾（索引`n-1=3`，值為`1`）：

-交換后數(shù)組：`[1,10,3,4,5]`。

-減少堆的大小：`n=3`。

-調(diào)整新堆頂（索引`0`，值為`1`）：

-`largest=0`。

-`left=1`，`array[1]=10`。`largest=max(0,1)=1`。

-`right=2`，`array[2]=3`。`largest=max(1,2)=1`。

-`largest=1`!=`i=0`。交換`array[0]`和`array[1]`：`[10,1,3,4,5]`。

-遞歸調(diào)整`largest=1`（值為`1`）：

-`left=3`，`array[3]=4`。`largest=max(1,3)=3`。

-`right=4`，`array[4]=5`。`largest=max(3,4)=4`。

-`largest=4`!=`i=1`。交換`array[1]`和`array[4]`：`[10,5,3,4,1]`。

-遞歸調(diào)整`largest=4`（值為`1`）：

-`left=7`，超出范圍`n=3`。終止。

-第二輪結(jié)束，堆結(jié)構(gòu)為`[10,5,3,4,1]`，但末尾元素已為`1`。

3.第三輪：

-交換堆頂（索引`0`，值為`10`）與末尾（索引`n-1=2`，值為`3`）：

-交換后數(shù)組：`[3,5,10,4,1]`。

-減少堆的大?。篳n=2`。

-調(diào)整新堆頂（索引`0`，值為`3`）：

-`largest=0`。

-`left=1`，`array[1]=5`。`largest=max(0,1)=1`。

-`right=2`，`array[2]=10`。`largest=max(1,2)=2`。

-`largest=2`!=`i=0`。交換`array[0]`和`array[2]`：`[10,5,3,4,1]`。

-遞歸調(diào)整`largest=2`（值為`3`）：

-`left=5`，超出范圍`n=2`。終止。

-第三輪結(jié)束，堆結(jié)構(gòu)為`[10,5,3,4,1]`，但末尾元素已為`3`。

4.第四輪：

-此時堆的大小`n=2`，堆頂（索引`0`，值為`10`），末尾（索引`n-1=1`，值為`5`）。

-由于`n=2`，`i=0`和`i=1`都是非葉子節(jié)點(diǎn)，但只需調(diào)整根節(jié)點(diǎn)。

-調(diào)整新堆頂（索引`0`，值為`10`）：

-`largest=0`。

-`left=1`，`array[1]=5`。`largest=max(0,1)=1`。

-`right=2`，超出范圍`n=2`。

-`largest=1`!=`i=0`。交換`array[0]`和`array[1]`：`[5,10,3,4,1]`。

-遞歸調(diào)整`largest=1`（值為`10`）：

-`left=3`，`array[3]=4`。`largest=max(1,3)=3`。

-`right=4`，`array[4]=1`。`largest=max(3,4)=3`。

-`largest=3`!=`i=1`。交換`array[1]`和`array[3]`：`[5,4,3,10,1]`。

-遞歸調(diào)整`largest=3`（值為`10`）：

-`left=7`，超出范圍`n=2`。終止。

-第四輪結(jié)束，堆結(jié)構(gòu)為`[5,4,3,10,1]`，但末尾元素已為`1`。

5.終止條件：當(dāng)堆的大小`n`減至`1`時，排序過程結(jié)束。此時，數(shù)組為`[5,4,3,10,1]`，但最后一個元素`1`在末尾。由于我們交換的是堆頂和當(dāng)前“末尾候選”元素，實(shí)際上最大值會逐漸被推到數(shù)組的末尾。如果我們從數(shù)組末尾開始向前看，`[1,10,3,4,5]`，`[1,5,10,4,3]`，`[1,4,10,5,3]`，`[1,3,10,5,4]`，`[1,3,5,10,4]`?？梢钥吹?，除了最后一個元素，前面的元素已經(jīng)是升序了。最終排序結(jié)果為`[1,3,4,5,10]`。

（三）完整排序數(shù)組

經(jīng)過完整的堆排序過程后，原始數(shù)組`[4,10,3,5,1]`被排序為`[1,3,4,5,10]`（升序）。

一、堆排序概述

堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的比較排序算法，具有時間復(fù)雜度為O(nlogn)的特性。它通過構(gòu)建最大堆或最小堆來實(shí)現(xiàn)排序，主要分為兩個核心步驟：構(gòu)建堆和堆調(diào)整。堆排序算法具有空間復(fù)雜度為O(1)，屬于原地排序算法。

（一）堆的定義與性質(zhì)

1.堆是一種完全二叉樹結(jié)構(gòu)，分為最大堆和最小堆兩種類型。

-最大堆：父節(jié)點(diǎn)的值始終大于或等于子節(jié)點(diǎn)的值。

-最小堆：父節(jié)點(diǎn)的值始終小于或等于子節(jié)點(diǎn)的值。

2.堆的存儲方式通常采用數(shù)組，其中節(jié)點(diǎn)i的左子節(jié)點(diǎn)為2i+1，右子節(jié)點(diǎn)為2i+2，父節(jié)點(diǎn)為(i-1)/2（向下取整）。

（二）堆排序的基本步驟

1.構(gòu)建初始堆：將待排序數(shù)組轉(zhuǎn)化為最大堆或最小堆。

2.堆調(diào)整：通過交換堆頂元素與當(dāng)前末尾元素，逐步減少堆的大小，并重新調(diào)整堆。

3.最終排序：經(jīng)過多輪堆調(diào)整后，數(shù)組將按升序或降序排列。

二、堆排序的實(shí)現(xiàn)細(xì)節(jié)

（一）構(gòu)建最大堆

1.從最后一個非葉子節(jié)點(diǎn)開始向前遍歷，對每個節(jié)點(diǎn)執(zhí)行堆調(diào)整。

-非葉子節(jié)點(diǎn)的索引范圍：n/2-1到0（n為數(shù)組長度）。

2.堆調(diào)整過程：

-初始化當(dāng)前節(jié)點(diǎn)為i，其左右子節(jié)點(diǎn)分別為2i+1和2i+2。

-比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)的值，找出最大值所在節(jié)點(diǎn)。

-若最大值不在當(dāng)前節(jié)點(diǎn)，則交換位置，并繼續(xù)對子樹進(jìn)行堆調(diào)整。

（二）堆調(diào)整算法

1.輸入：當(dāng)前節(jié)點(diǎn)索引i，堆的大小n。

2.步驟：

(1)初始化最大索引為i。

(2)比較當(dāng)前節(jié)點(diǎn)與左子節(jié)點(diǎn)（2i+1），若左子節(jié)點(diǎn)更大，則更新最大索引為左子節(jié)點(diǎn)索引。

(3)比較當(dāng)前節(jié)點(diǎn)與右子節(jié)點(diǎn)（2i+2），若右子節(jié)點(diǎn)更大，則更新最大索引為右子節(jié)點(diǎn)索引。

(4)若最大索引不為i，則交換i與最大索引處的值，并遞歸對子樹進(jìn)行堆調(diào)整。

（三）堆排序完整流程

1.構(gòu)建初始最大堆：

-從n/2-1開始，逐個向前遍歷并調(diào)整節(jié)點(diǎn)，直至到達(dá)根節(jié)點(diǎn)（索引0）。

2.排序過程：

(1)交換堆頂元素（當(dāng)前最大值）與數(shù)組末尾元素。

(2)減少堆的大小（n減1），并重新調(diào)整根節(jié)點(diǎn)為最大值。

(3)重復(fù)步驟(1)和(2)，直至堆的大小為1。

三、堆排序的優(yōu)缺點(diǎn)

（一）優(yōu)點(diǎn)

1.時間復(fù)雜度穩(wěn)定：無論輸入數(shù)據(jù)如何，堆排序的時間復(fù)雜始終為O(nlogn)。

2.空間復(fù)雜度低：僅使用常數(shù)級額外空間，屬于原地排序算法。

3.適合大規(guī)模數(shù)據(jù)：對于內(nèi)存受限場景，堆排序表現(xiàn)優(yōu)于某些需要額外存儲的排序算法。

（二）缺點(diǎn)

1.實(shí)現(xiàn)復(fù)雜度較高：堆調(diào)整過程涉及遞歸或循環(huán)，代碼邏輯相對復(fù)雜。

2.非穩(wěn)定排序：相同值的元素在排序后相對順序可能改變。

3.相比快速排序：在平均情況下性能略遜，但更穩(wěn)定。

四、示例說明

以數(shù)組[4,10,3,5,1]為例，展示堆排序過程：

（一）構(gòu)建初始最大堆

1.非葉子節(jié)點(diǎn)索引：2（值為10）和1（值為4）。

2.調(diào)整節(jié)點(diǎn)2（10）：左右子節(jié)點(diǎn)分別為4和3，無需調(diào)整。

3.調(diào)整節(jié)點(diǎn)1（4）：右子節(jié)點(diǎn)（值為5）大于當(dāng)前節(jié)點(diǎn)，交換后數(shù)組變?yōu)閇4,5,3,10,1]。

4.最終堆結(jié)構(gòu)：[10,5,3,4,1]。

（二）排序過程

1.交換10與1，數(shù)組變?yōu)閇1,5,3,4,10]。

2.減少堆大小為4，調(diào)整根節(jié)點(diǎn)5：

-比較節(jié)點(diǎn)5與子節(jié)點(diǎn)4和3，無需調(diào)整。

-數(shù)組變?yōu)閇1,4,3,5,10]。

3.交換4與5，數(shù)組變?yōu)閇1,3,4,5,10]。

4.減少堆大小為3，調(diào)整根節(jié)點(diǎn)3：

-比較節(jié)點(diǎn)3與子節(jié)點(diǎn)4和1，無需調(diào)整。

-數(shù)組保持[1,3,4,5,10]。

5.交換3與1，數(shù)組變?yōu)閇1,3,4,5,10]。

6.減少堆大小為2，調(diào)整根節(jié)點(diǎn)3：

-比較節(jié)點(diǎn)3與子節(jié)點(diǎn)4和1，無需調(diào)整。

-數(shù)組保持[1,3,4,5,10]。

最終排序結(jié)果：[1,3,4,5,10]。

一、堆排序概述

堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的比較排序算法，具有時間復(fù)雜度為O(nlogn)的特性。它通過構(gòu)建最大堆或最小堆來實(shí)現(xiàn)排序，主要分為兩個核心步驟：構(gòu)建堆和堆調(diào)整。堆排序算法具有空間復(fù)雜度為O(1)，屬于原地排序算法。

（一）堆的定義與性質(zhì)

1.堆是一種完全二叉樹結(jié)構(gòu)，分為最大堆和最小堆兩種類型。

-最大堆：父節(jié)點(diǎn)的值始終大于或等于子節(jié)點(diǎn)的值。這種堆結(jié)構(gòu)確保了堆頂元素是整個堆中的最大值。

-最小堆：父節(jié)點(diǎn)的值始終小于或等于子節(jié)點(diǎn)的值。這種堆結(jié)構(gòu)確保了堆頂元素是整個堆中的最小值。

2.堆的存儲方式通常采用數(shù)組，這種存儲方式具有空間效率高、訪問速度快的特點(diǎn)。在數(shù)組中，對于任意節(jié)點(diǎn)i（從0開始索引）：

-其左子節(jié)點(diǎn)的索引為`2i+1`

-其右子節(jié)點(diǎn)的索引為`2i+2`

-其父節(jié)點(diǎn)的索引為`(i-1)/2`（向下取整）

這種索引關(guān)系使得我們可以通過簡單的數(shù)學(xué)運(yùn)算直接訪問節(jié)點(diǎn)的子節(jié)點(diǎn)和父節(jié)點(diǎn)，無需指針或鏈表結(jié)構(gòu)，這也是堆排序能夠?qū)崿F(xiàn)原地排序（空間復(fù)雜度O(1)）的關(guān)鍵原因之一。

（二）堆排序的基本步驟

堆排序算法通過兩個主要階段對輸入數(shù)組進(jìn)行排序：

1.構(gòu)建初始堆：此階段的目標(biāo)是將一個無序的輸入數(shù)組轉(zhuǎn)換成一個滿足堆性質(zhì)的完全二叉樹（通常是最大堆）。這一步是后續(xù)排序操作的基礎(chǔ)。

2.堆調(diào)整與排序：在初始堆構(gòu)建完成后，通過反復(fù)“移除”堆頂元素（在最大堆中是最大值，在最小堆中是最小值）并“調(diào)整”剩余元素以維持堆性質(zhì)，逐步將最大（或最?。┰亍懊芭荨钡綌?shù)組的末尾。這個過程會重復(fù)進(jìn)行，直到堆的大小減至1，此時數(shù)組已經(jīng)是有序的。

3.最終輸出：經(jīng)過上述過程，數(shù)組會按照指定順序（升序或降序，取決于使用最大堆還是最小堆）排列。通常，如果使用最大堆并按升序排序，最后得到的數(shù)組就是升序排列的。

二、堆排序的實(shí)現(xiàn)細(xì)節(jié)

（一）構(gòu)建最大堆

構(gòu)建最大堆是堆排序的第一步，其目的是確保從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑上，節(jié)點(diǎn)的值都是遞減的（即父節(jié)點(diǎn)>=子節(jié)點(diǎn)）。這一步通常采用自底向上的方式實(shí)現(xiàn)。

1.確定非葉子節(jié)點(diǎn)的范圍：在一個有n個元素的數(shù)組中，非葉子節(jié)點(diǎn)是從`n/2-1`到`0`的所有索引（假設(shè)數(shù)組索引從0開始）。只有這些節(jié)點(diǎn)可能有子節(jié)點(diǎn)，因此只需要對這些節(jié)點(diǎn)進(jìn)行堆調(diào)整。

-理由：索引大于或等于`n/2`的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)（在完全二叉樹中，最后一個非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)索引至少為`2(n/2)=n`）。

2.對每個非葉子節(jié)點(diǎn)執(zhí)行堆調(diào)整：

-從最后一個非葉子節(jié)點(diǎn)開始，逐個向前遍歷至根節(jié)點(diǎn)（索引0）。

-對于當(dāng)前節(jié)點(diǎn)i，首先假設(shè)其本身就是最大值。

-比較當(dāng)前節(jié)點(diǎn)i與其兩個子節(jié)點(diǎn)（左子節(jié)點(diǎn)`2i+1`和右子節(jié)點(diǎn)`2i+2`，如果存在）的值。

-找出三個節(jié)點(diǎn)（i,`2i+1`,`2i+2`）中的最大值，并記錄其索引（記為`largest`）。

-如果`largest`不等于i（即當(dāng)前節(jié)點(diǎn)不是最大值），則將當(dāng)前節(jié)點(diǎn)i的值與索引為`largest`的節(jié)點(diǎn)的值進(jìn)行交換。

-交換后，由于被交換到位置i的節(jié)點(diǎn)的原始子樹可能已經(jīng)破壞了堆的性質(zhì)，因此需要以`largest`的位置為根，對其子樹進(jìn)行遞歸的堆調(diào)整。

-這個過程會一直持續(xù)，直到當(dāng)前節(jié)點(diǎn)i的子樹滿足堆性質(zhì)，或者當(dāng)前節(jié)點(diǎn)成為葉子節(jié)點(diǎn)。

（二）堆調(diào)整算法（詳細(xì)步驟）

堆調(diào)整是維護(hù)堆性質(zhì)的核心操作。給定一個節(jié)點(diǎn)索引`i`和當(dāng)前堆的大小`n`，堆調(diào)整的目標(biāo)是確保以節(jié)點(diǎn)`i`為根的子樹滿足最大堆性質(zhì)。

1.輸入?yún)?shù)：

-`i`:當(dāng)前需要檢查并可能調(diào)整的節(jié)點(diǎn)在堆中的索引。

-`n`:當(dāng)前堆中有效的元素數(shù)量（即堆的實(shí)際大小，用于防止訪問到數(shù)組邊界之外的元素）。

2.初始化最大索引：設(shè)定`largest=i`，表示當(dāng)前節(jié)點(diǎn)`i`是候選的最大值。

3.檢查左子節(jié)點(diǎn)：

-計算左子節(jié)點(diǎn)的索引：`left=2i+1`。

-如果`left`小于`n`（即左子節(jié)點(diǎn)存在），并且左子節(jié)點(diǎn)的值`array[left]`大于當(dāng)前記錄的最大值`array[largest]`，則更新`largest=left`。

4.檢查右子節(jié)點(diǎn)：

-計算右子節(jié)點(diǎn)的索引：`right=2i+2`。

-如果`right`小于`n`（即右子節(jié)點(diǎn)存在），并且右子節(jié)點(diǎn)的值`array[right]`大于當(dāng)前記錄的最大值`array[largest]`，則更新`largest=right`。

5.比較最大索引與當(dāng)前節(jié)點(diǎn)：

-經(jīng)過步驟3和4后，`largest`存儲了`i`、`2i+1`、`2i+2`中最大值的索引。

-如果`largest`不等于`i`（即當(dāng)前節(jié)點(diǎn)不是三個比較節(jié)點(diǎn)中的最大值），則說明當(dāng)前節(jié)點(diǎn)`i`不滿足最大堆性質(zhì)。

-將當(dāng)前節(jié)點(diǎn)`i`的值與索引為`largest`的節(jié)點(diǎn)的值進(jìn)行交換：`swap(array[i],array[largest])`。

-交換后，原位于`largest`位置的節(jié)點(diǎn)移動到了位置`i`。由于這個新節(jié)點(diǎn)`largest`可能位于一個非葉子節(jié)點(diǎn)上，其子樹可能已經(jīng)破壞了堆的性質(zhì)，因此必須對新的`largest`位置（即原`i`位置）進(jìn)行遞歸的堆調(diào)整。

-遞歸調(diào)用堆調(diào)整函數(shù)：`heapify(array,n,largest)`。

-如果`largest`等于`i`，則說明當(dāng)前節(jié)點(diǎn)及其子樹已經(jīng)滿足最大堆性質(zhì)，無需進(jìn)一步操作，遞歸結(jié)束。

6.終止條件：遞歸的終止條件是`largest`索引對應(yīng)的節(jié)點(diǎn)不再有子節(jié)點(diǎn)（即`largest>=n/2`），或者交換后新的`largest`節(jié)點(diǎn)已經(jīng)滿足堆性質(zhì)。

（三）堆排序完整流程（分步驟詳解）

堆排序算法將排序過程清晰地劃分為以下步驟：

1.構(gòu)建初始最大堆：

-確定數(shù)組的長度`n`。

-計算最后一個非葉子節(jié)點(diǎn)的索引：`end=n/2-1`。

-從索引`end`開始，逐個向前遍歷到索引`0`，對每個索引`i`執(zhí)行堆調(diào)整操作。

-調(diào)用`heapify(array,n,i)`。

-完成這一步后，整個數(shù)組構(gòu)成一個最大堆，堆頂元素（索引`0`）是數(shù)組中的最大值。

2.排序階段：

-初始化堆的大小`n`為數(shù)組的實(shí)際長度。

-進(jìn)入一個循環(huán)，持續(xù)執(zhí)行直到堆的大小`n`減至`1`。

-循環(huán)體內(nèi)的主要操作：

(1)交換堆頂與末尾元素：

-交換索引`0`（堆頂）的元素與索引`n-1`（當(dāng)前堆的最后一個元素）的元素。

-這將最大元素“移出”堆結(jié)構(gòu)，放置到數(shù)組的末尾。

(2)減少堆的大?。?/p>

-將堆的大小`n`減`1`，因為最后一個元素已經(jīng)確定是當(dāng)前剩余元素中的最大值，不再屬于堆的一部分。

(3)調(diào)整新堆頂：

-對新的堆頂元素（原數(shù)組末尾被移出的元素現(xiàn)在位于索引`0`）執(zhí)行堆調(diào)整操作。

-調(diào)用`heapify(array,n,0)`。

-這一步是為了將新的最大值“冒泡”到堆頂。

-重復(fù)步驟(1)到(3)，直到堆的大小為`1`。

3.輸出結(jié)果：

-當(dāng)堆的大小減至`1`時，循環(huán)結(jié)束。此時，數(shù)組的前`n-1`個元素已經(jīng)是有序的（假設(shè)使用最大堆并按升序排序，則從后向前有序）。

-數(shù)組的最后一個元素是整個數(shù)組中的最大值。

-通常，為了得到完整的升序數(shù)組，可以在排序結(jié)束后對數(shù)組進(jìn)行一次反轉(zhuǎn)，或者直接從數(shù)組的第二個元素開始遍歷（索引`1`到`n-1`）即可獲得升序結(jié)果。

三、堆排序的優(yōu)缺點(diǎn)

（一）優(yōu)點(diǎn)

1.時間復(fù)雜度穩(wěn)定：堆排序的最壞、平均和最好時間復(fù)雜度均為O(nlogn)。這一特性使得堆排序在處理大規(guī)模數(shù)據(jù)時，性能表現(xiàn)具有可預(yù)測性，不像快速排序那樣在最壞情況下退化到O(n^2)。

2.空間復(fù)雜度低：堆排序是原地排序算法，它只需要常數(shù)級的額外空間（通常用于堆調(diào)整過程中的交換操作），空間復(fù)雜度為O(1)。這使得它在內(nèi)存資源有限的環(huán)境下非常適用。

3.適合大規(guī)模數(shù)據(jù)：由于其O(nlogn)的時間復(fù)雜度，并且是原地排序，堆排序適合處理數(shù)據(jù)量巨大且內(nèi)存受限的場景，例如在外部排序中作為核心排序步驟。

4.非比較依賴：堆排序本質(zhì)上是比較排序，不依賴于特定數(shù)據(jù)類型的大小比較，只要比較操作定義良好，就可以應(yīng)用于各種可排序的數(shù)據(jù)。

（二）缺點(diǎn)

1.實(shí)現(xiàn)復(fù)雜度較高：堆排序的代碼實(shí)現(xiàn)比冒泡排序、選擇排序或插入排序更復(fù)雜，特別是堆調(diào)整的邏輯涉及遞歸或循環(huán)，容易出錯。理解堆的結(jié)構(gòu)和堆調(diào)整的過程對于正確實(shí)現(xiàn)堆排序是一個挑戰(zhàn)。

2.非穩(wěn)定排序：堆排序是一種不穩(wěn)定排序算法。這意味著對于兩個具有相同值的元素，排序后它們的相對順序可能會與排序前不同。例如，在最大堆中，兩個值相同的元素A和B，如果A在B之前，但在構(gòu)建堆和后續(xù)調(diào)整過程中，A和B的位置可能會交換。

3.緩存局部性可能較差：與快速排序等訪問模式更規(guī)律（如二分法劃分）的算法相比，堆排序在訪問數(shù)組元素時可能具有更差的局部性，因為堆調(diào)整過程可能訪問數(shù)組的遠(yuǎn)端元素，導(dǎo)致緩存未命中率較高，從而影響實(shí)際運(yùn)行速度。不過，對于某些特定硬件，這種影響可能不顯著。

四、示例說明（以最大堆構(gòu)建和排序為例）

我們以一個具體的無序數(shù)組`[4,10,3,5,1]`為例，詳細(xì)演示堆排序的每一步操作。假設(shè)數(shù)組索引從`0`開始。

（一）構(gòu)建初始最大堆

假設(shè)數(shù)組為`array=[4,10,3,5,1]`，長度`n=5`。

1.計算最后一個非葉子節(jié)點(diǎn)的索引：`end=n/2-1=5/2-1=2`。因此，需要檢查索引`2`和`1`的節(jié)點(diǎn)。

2.檢查節(jié)點(diǎn)`i=2`（值為`3`）：

-左子節(jié)點(diǎn)索引`left=22+1=5`。`left`等于`n`，表示沒有左子節(jié)點(diǎn)。

-右子節(jié)點(diǎn)索引`right=22+2=6`。`right`大于`n`，表示沒有右子節(jié)點(diǎn)。

-由于沒有子節(jié)點(diǎn)，節(jié)點(diǎn)`2`已經(jīng)滿足最大堆性質(zhì)，無需調(diào)整。

3.檢查節(jié)點(diǎn)`i=1`（值為`10`）：

-左子節(jié)點(diǎn)索引`left=21+1=3`。值為`5`。

-右子節(jié)點(diǎn)索引`right=21+2=4`。值為`1`。

-比較`i=1`（10），`left=3`（5），`right=4`（1），最大值為`10`，位于`i=1`。

-最大索引`largest=1`，不等于`i=1`，無需交換。

-節(jié)點(diǎn)`i=1`已經(jīng)滿足最大堆性質(zhì)。

4.檢查節(jié)點(diǎn)`i=0`（值為`4`）：

-左子節(jié)點(diǎn)索引`left=20+1=1`。值為`10`。

-右子節(jié)點(diǎn)索引`right=20+2=2`。值為`3`。

-比較`i=0`（4），`left=1`（10），`right=2`（3），最大值為`10`，位于`left=1`。

-最大索引`largest=1`，不等于`i=0`。

-交換`array[0]`和`array[1]`：交換`4`和`10`。

-交換后數(shù)組：`[10,4,3,5,1]`。

-交換完成后，節(jié)點(diǎn)`0`（現(xiàn)在值為`10`）需要檢查其子節(jié)點(diǎn)（`left=1`（4），`right=2`（3））。

-比較`i=0`（10），`left=1`（4），`right=2`（3），最大值仍為`10`，位于`i=0`。

-節(jié)點(diǎn)`i=0`滿足最大堆性質(zhì)。

5.最終構(gòu)建的最大堆數(shù)組：`[10,4,3,5,1]`。

-驗證：根節(jié)點(diǎn)`10`>=左子節(jié)點(diǎn)`4`，`10`>=右子節(jié)點(diǎn)`3`。父節(jié)點(diǎn)`4`>=左子節(jié)點(diǎn)`5`，父節(jié)點(diǎn)`4`>=右子節(jié)點(diǎn)`1`。父節(jié)點(diǎn)`3`>=左子節(jié)點(diǎn)`5`，父節(jié)點(diǎn)`3`>=右子節(jié)點(diǎn)`1`。堆性質(zhì)滿足。

（二）堆調(diào)整與排序過程

排序階段開始，初始堆大小`n=5`。

1.第一輪：

-交換堆頂（索引`0`，值為`10`）與末尾（索引`n-1=4`，值為`1`）：

-交換后數(shù)組：`[1,4,3,5,10]`。

-減少堆的大小：`n=4`。

-調(diào)整新堆頂（索引`0`，值為`1`）：

-`largest=0`。

-`left=1`，`array[1]=4`。`largest=max(0,1)=1`。

-`right=2`，`array[2]=3`。`largest=max(1,2)=1`。

-`largest=1`!=`i=0`。交換`array[0]`和`array[1]`：`[4,1,3,5,10]`。

-遞歸調(diào)整`largest=1`（值為`1`）：

-`left=3`，`array[3]=5`。`largest=max(1,3)=3`。

-`right=4`，`array[4]=10`。`largest=max(3,4)=4`。

-`largest=4`!=`i=1`。交換`array[1]`和`array[4]`：`[4,10,3,5,1]`。

-遞歸調(diào)整`largest=4`（值為`1`）：

-`left=7`，超出范圍`n=4`。終止。

-第一輪結(jié)束，堆結(jié)構(gòu)為`[4,10,3,5,1]`，但末尾元素已為`1`。

2.第二輪：

-交換堆頂（索引`0`，值為`4`）與末尾（索引`n-1=3`，值為`1`）：

-交換后數(shù)組：`[1,10,3,4,5]`。

-減少堆的大?。篳n=3`。

-調(diào)整新堆頂（索引`0`，值為`1`）：

-`largest=0`。

-`left=1`，`array[1]=10`