堆的調(diào)整規(guī)則總結(jié)一、堆的基本概念

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常用數(shù)組實(shí)現(xiàn)。堆具有以下關(guān)鍵特性：

（一）堆形狀特性

1.堆必須是一棵完全二叉樹。

2.完全二叉樹的定義：除最后一層外，每一層都是滿的，且最后一層節(jié)點(diǎn)從左到右連續(xù)排列。

（二）堆值特性

1.最大堆（MaxHeap）：父節(jié)點(diǎn)值始終大于或等于子節(jié)點(diǎn)值。

2.最小堆（MinHeap）：父節(jié)點(diǎn)值始終小于或等于子節(jié)點(diǎn)值。

二、堆的調(diào)整規(guī)則

堆的調(diào)整是指將一個無序的數(shù)組重新排列成符合堆特性的結(jié)構(gòu)。調(diào)整分為兩種場景：

（一）從無序數(shù)組構(gòu)建堆

1.自底向上調(diào)整（Bottom-UpHeapify）

（1）從最后一個非葉子節(jié)點(diǎn)開始調(diào)整。

（2）每個節(jié)點(diǎn)依次向上調(diào)整至根節(jié)點(diǎn)，確保滿足堆特性。

（3）調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為最后一個非葉子節(jié)點(diǎn)。

b.比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)，找到最大（或最小）值節(jié)點(diǎn)。

c.若當(dāng)前節(jié)點(diǎn)不是最大（或最?。┲?，則與最大（或最?。┲倒?jié)點(diǎn)交換。

d.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)，重復(fù)b-c步驟，直到到達(dá)根節(jié)點(diǎn)。

2.自頂向下調(diào)整（Top-DownHeapify）

（1）從根節(jié)點(diǎn)開始調(diào)整。

（2）每個節(jié)點(diǎn)依次向下調(diào)整至葉子節(jié)點(diǎn)，確保滿足堆特性。

（3）調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)。

b.比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)，找到最大（或最?。┲倒?jié)點(diǎn)。

c.若當(dāng)前節(jié)點(diǎn)不是最大（或最?。┲?，則與最大（或最?。┲倒?jié)點(diǎn)交換。

d.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)，重復(fù)b-c步驟，直到到達(dá)葉子節(jié)點(diǎn)。

（二）堆的插入操作

1.插入步驟

（1）將新元素添加到數(shù)組的末尾（保持完全二叉樹形狀）。

（2）通過上浮調(diào)整（BubbleUp）將新元素與父節(jié)點(diǎn)比較并交換，直到滿足堆特性。

（3）上浮調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為插入位置。

b.比較當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)，若不滿足堆特性則交換。

c.將當(dāng)前節(jié)點(diǎn)更新為被交換的父節(jié)點(diǎn)，重復(fù)a-b步驟，直到到達(dá)根節(jié)點(diǎn)或滿足堆特性。

（三）堆的刪除操作

1.刪除步驟

（1）將根節(jié)點(diǎn)替換為數(shù)組的最后一個元素（保持完全二叉樹形狀）。

（2）通過下沉調(diào)整（BubbleDown）將根節(jié)點(diǎn)與子節(jié)點(diǎn)比較并交換，直到滿足堆特性。

（3）下沉調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)。

b.比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)，找到最大（或最?。┲倒?jié)點(diǎn)。

c.若當(dāng)前節(jié)點(diǎn)不是最大（或最小）值，則與最大（或最?。┲倒?jié)點(diǎn)交換。

d.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)，重復(fù)a-c步驟，直到到達(dá)葉子節(jié)點(diǎn)或滿足堆特性。

三、堆調(diào)整的效率分析

（一）時(shí)間復(fù)雜度

1.從無序數(shù)組構(gòu)建堆：

-自底向上調(diào)整：O(n)，其中n為節(jié)點(diǎn)數(shù)量。

-自頂向下調(diào)整：O(nlogn)，效率較低。

2.插入操作：O(logn)，需上浮調(diào)整。

3.刪除操作：O(logn)，需下沉調(diào)整。

（二）空間復(fù)雜度

1.所有操作均原地修改數(shù)組，空間復(fù)雜度為O(1)。

四、應(yīng)用場景

1.優(yōu)先隊(duì)列實(shí)現(xiàn)。

2.堆排序算法的基礎(chǔ)。

3.貪心算法中的狀態(tài)管理。

4.圖算法中的最小/最大生成樹計(jì)算。

一、堆的基本概念

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常用數(shù)組實(shí)現(xiàn)。堆具有以下關(guān)鍵特性：

（一）堆形狀特性

1.堆必須是一棵完全二叉樹。

-完全二叉樹的定義：除最后一層外，每一層都是滿的，且最后一層節(jié)點(diǎn)從左到右連續(xù)排列。

-數(shù)組表示法中，節(jié)點(diǎn)的索引與其子節(jié)點(diǎn)索引存在固定關(guān)系，便于快速訪問。

-對于索引為i的節(jié)點(diǎn)：

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

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

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

（二）堆值特性

1.最大堆（MaxHeap）：父節(jié)點(diǎn)值始終大于或等于子節(jié)點(diǎn)值。

-應(yīng)用場景：快速獲取最大值。

-示例：在數(shù)組中，根節(jié)點(diǎn)（索引0）存儲最大值。

2.最小堆（MinHeap）：父節(jié)點(diǎn)值始終小于或等于子節(jié)點(diǎn)值。

-應(yīng)用場景：快速獲取最小值。

-示例：在數(shù)組中，根節(jié)點(diǎn)（索引0）存儲最小值。

三、堆的調(diào)整規(guī)則

堆的調(diào)整是指將一個無序的數(shù)組重新排列成符合堆特性的結(jié)構(gòu)。調(diào)整分為兩種場景：

（一）從無序數(shù)組構(gòu)建堆

1.自底向上調(diào)整（Bottom-UpHeapify）

-適用于從空堆逐步添加元素，或從完全二叉樹的葉子節(jié)點(diǎn)向上構(gòu)建堆。

-優(yōu)勢：時(shí)間復(fù)雜度為O(n)，效率較高。

-具體步驟：

（1）確定起始調(diào)整節(jié)點(diǎn)：

-從最后一個非葉子節(jié)點(diǎn)開始調(diào)整。

-非葉子節(jié)點(diǎn)計(jì)算公式：`start_index=(n-2)/2`，其中n為數(shù)組長度。

（2）逐個節(jié)點(diǎn)向上調(diào)整：

-從`start_index`開始，依次向上遍歷至根節(jié)點(diǎn)（索引0）。

-對于每個節(jié)點(diǎn)i：

a.比較與交換：

-比較節(jié)點(diǎn)i與其左右子節(jié)點(diǎn)（`2i+1`和`2i+2`）。

-找出三個節(jié)點(diǎn)中的最大值（在最大堆中），或最小值（在最小堆中）。

-若節(jié)點(diǎn)i不是最大/最小值，則與最大/最小子節(jié)點(diǎn)交換。

b.更新當(dāng)前節(jié)點(diǎn)：

-將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)（交換后子節(jié)點(diǎn)可能不再滿足堆特性）。

-重復(fù)比較與交換，直到節(jié)點(diǎn)i為葉子節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)遍歷至根節(jié)點(diǎn)且所有節(jié)點(diǎn)均滿足堆特性時(shí)，構(gòu)建完成。

2.自頂向下調(diào)整（Top-DownHeapify）

-適用于從有序數(shù)組轉(zhuǎn)換為堆，或刪除根節(jié)點(diǎn)后重新調(diào)整。

-優(yōu)勢：代碼實(shí)現(xiàn)簡單，但時(shí)間復(fù)雜度為O(nlogn)，效率較低。

-具體步驟：

（1）初始化當(dāng)前節(jié)點(diǎn)：

-從根節(jié)點(diǎn)（索引0）開始。

（2）逐個節(jié)點(diǎn)向下調(diào)整：

-對于每個節(jié)點(diǎn)i：

a.比較與交換：

-比較節(jié)點(diǎn)i與其左右子節(jié)點(diǎn)。

-找出最大/最小子節(jié)點(diǎn)。

-若節(jié)點(diǎn)i不是最大/最小值，則與最大/最小子節(jié)點(diǎn)交換。

b.更新當(dāng)前節(jié)點(diǎn)：

-將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)。

-重復(fù)比較與交換，直到當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)遍歷至最后一個葉子節(jié)點(diǎn)且所有節(jié)點(diǎn)均滿足堆特性時(shí)，調(diào)整完成。

（二）堆的插入操作

1.插入步驟

-目標(biāo)：將一個新元素添加到堆中，并保持堆特性。

-具體步驟：

（1）添加元素：

-將新元素添加到數(shù)組的末尾（保持完全二叉樹形狀）。

-例如，在最大堆中，新元素初始值可能小于根節(jié)點(diǎn)，需要調(diào)整。

（2）上浮調(diào)整（BubbleUp）：

-初始化當(dāng)前節(jié)點(diǎn)為插入位置（數(shù)組末尾）。

-比較當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)：

a.若當(dāng)前節(jié)點(diǎn)值大于父節(jié)點(diǎn)值（最大堆），或小于父節(jié)點(diǎn)值（最小堆），則交換。

b.若不滿足交換條件，則停止調(diào)整。

-將當(dāng)前節(jié)點(diǎn)更新為被交換的父節(jié)點(diǎn)，重復(fù)比較與交換，直到到達(dá)根節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，或父節(jié)點(diǎn)值大于/小于當(dāng)前節(jié)點(diǎn)值時(shí)，插入完成。

（三）堆的刪除操作

1.刪除步驟

-目標(biāo)：刪除堆頂元素（根節(jié)點(diǎn)），并保持堆特性。

-具體步驟：

（1）替換根節(jié)點(diǎn)：

-將數(shù)組的最后一個元素移動到根節(jié)點(diǎn)位置（覆蓋原根節(jié)點(diǎn)）。

-數(shù)組長度減1，保持完全二叉樹形狀。

（2）下沉調(diào)整（BubbleDown）：

-初始化當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)。

-比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)：

a.找出最大/最小子節(jié)點(diǎn)。

b.若當(dāng)前節(jié)點(diǎn)不是最大/最小值，則與最大/最小子節(jié)點(diǎn)交換。

c.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)。

-重復(fù)比較與交換，直到當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，或左右子節(jié)點(diǎn)不存在（即無子節(jié)點(diǎn)），下沉調(diào)整完成。

三、堆調(diào)整的效率分析

（一）時(shí)間復(fù)雜度

1.從無序數(shù)組構(gòu)建堆：

-自底向上調(diào)整：O(n)，可通過數(shù)學(xué)證明優(yōu)化。

-自頂向下調(diào)整：O(nlogn)，適用于少量節(jié)點(diǎn)調(diào)整。

2.插入操作：O(logn)，需上浮調(diào)整。

3.刪除操作：O(logn)，需下沉調(diào)整。

（二）空間復(fù)雜度

1.所有操作均原地修改數(shù)組，空間復(fù)雜度為O(1)。

四、堆調(diào)整的優(yōu)化技巧

（一）減少比較次數(shù)

1.提前終止：

-在上浮/下沉調(diào)整中，若交換后父節(jié)點(diǎn)/子節(jié)點(diǎn)值相等，可提前終止。

2.懶惰比較：

-記錄最后一次交換的位置，后續(xù)調(diào)整僅在該位置以下進(jìn)行比較。

（二）避免重復(fù)計(jì)算

1.緩存子節(jié)點(diǎn)值：

-在下沉調(diào)整中，可先計(jì)算左右子節(jié)點(diǎn)值，再進(jìn)行比較，避免多次訪問子節(jié)點(diǎn)。

2.索引偏移：

-對于固定大小的數(shù)組，可預(yù)計(jì)算父/子節(jié)點(diǎn)索引偏移量，減少除法運(yùn)算。

（三）并行化處理

1.分塊調(diào)整：

-將堆劃分為多個區(qū)塊，并行執(zhí)行上浮/下沉調(diào)整。

-注意邊界處理，確保區(qū)塊間調(diào)整順序正確。

2.GPU加速：

-利用GPU并行計(jì)算能力，加速大規(guī)模堆調(diào)整。

五、堆調(diào)整的常見問題

（一）數(shù)組越界問題

1.檢查子節(jié)點(diǎn)索引：

-在比較子節(jié)點(diǎn)前，驗(yàn)證索引是否在數(shù)組范圍內(nèi)。

-示例：`if(2i+1<n)`。

2.邊界處理：

-單子節(jié)點(diǎn)（如只有左子節(jié)點(diǎn)）時(shí)，比較邏輯需調(diào)整。

（二）調(diào)整順序問題

1.自底向上vs自頂向下：

-選擇合適的調(diào)整方式取決于應(yīng)用場景。

-自底向上適用于動態(tài)添加元素，自頂向下適用于靜態(tài)調(diào)整。

（三）堆類型混淆

1.明確堆類型：

-最大堆和最小堆操作相反，需避免混淆。

-示例：最大堆插入時(shí)，若新元素大于父節(jié)點(diǎn)，則上??；最小堆則相反。

六、堆調(diào)整的應(yīng)用場景

（一）優(yōu)先隊(duì)列實(shí)現(xiàn)

1.任務(wù)調(diào)度：

-按任務(wù)優(yōu)先級（如緊急程度）排序，優(yōu)先處理高優(yōu)先級任務(wù)。

-插入新任務(wù)時(shí)，O(logn)時(shí)間調(diào)整隊(duì)列。

2.事件處理：

-在游戲引擎中，按事件發(fā)生時(shí)間排序，實(shí)時(shí)響應(yīng)事件。

（二）堆排序算法

1.排序步驟：

a.構(gòu)建最大堆（或最小堆）。

b.重復(fù)執(zhí)行以下操作：

-刪除根節(jié)點(diǎn)（最大值），移至數(shù)組末尾。

-調(diào)整數(shù)組，重新構(gòu)建堆。

c.最終數(shù)組為有序序列。

2.時(shí)間復(fù)雜度：

-構(gòu)建堆：O(n)。

-n次刪除操作：O(nlogn)。

-總復(fù)雜度：O(nlogn)。

（三）圖算法輔助

1.Dijkstra算法優(yōu)化：

-使用最小堆管理待訪問節(jié)點(diǎn)，按距離排序。

-插入/刪除節(jié)點(diǎn)時(shí)，O(logn)時(shí)間更新優(yōu)先級。

2.A搜索算法：

-結(jié)合啟發(fā)式函數(shù)，使用最大堆優(yōu)先處理最優(yōu)路徑候選。

（四）動態(tài)數(shù)據(jù)管理

1.最大/最小元素緩存：

-實(shí)時(shí)維護(hù)數(shù)據(jù)流中的最大/最小值。

-插入新元素時(shí)，O(logn)時(shí)間更新堆頂。

2.TopK問題：

-快速找到數(shù)據(jù)集中前K個最大/最小元素。

-使用大小為K的最小堆，遍歷數(shù)據(jù)：

a.若堆未滿，直接插入。

b.若堆滿且當(dāng)前元素大于堆頂，替換堆頂并下沉調(diào)整。

-最終堆頂為第K大/小值。

一、堆的基本概念

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常用數(shù)組實(shí)現(xiàn)。堆具有以下關(guān)鍵特性：

（一）堆形狀特性

1.堆必須是一棵完全二叉樹。

2.完全二叉樹的定義：除最后一層外，每一層都是滿的，且最后一層節(jié)點(diǎn)從左到右連續(xù)排列。

（二）堆值特性

1.最大堆（MaxHeap）：父節(jié)點(diǎn)值始終大于或等于子節(jié)點(diǎn)值。

2.最小堆（MinHeap）：父節(jié)點(diǎn)值始終小于或等于子節(jié)點(diǎn)值。

二、堆的調(diào)整規(guī)則

堆的調(diào)整是指將一個無序的數(shù)組重新排列成符合堆特性的結(jié)構(gòu)。調(diào)整分為兩種場景：

（一）從無序數(shù)組構(gòu)建堆

1.自底向上調(diào)整（Bottom-UpHeapify）

（1）從最后一個非葉子節(jié)點(diǎn)開始調(diào)整。

（2）每個節(jié)點(diǎn)依次向上調(diào)整至根節(jié)點(diǎn)，確保滿足堆特性。

（3）調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為最后一個非葉子節(jié)點(diǎn)。

b.比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)，找到最大（或最?。┲倒?jié)點(diǎn)。

c.若當(dāng)前節(jié)點(diǎn)不是最大（或最?。┲?，則與最大（或最?。┲倒?jié)點(diǎn)交換。

d.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)，重復(fù)b-c步驟，直到到達(dá)根節(jié)點(diǎn)。

2.自頂向下調(diào)整（Top-DownHeapify）

（1）從根節(jié)點(diǎn)開始調(diào)整。

（2）每個節(jié)點(diǎn)依次向下調(diào)整至葉子節(jié)點(diǎn)，確保滿足堆特性。

（3）調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)。

b.比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)，找到最大（或最?。┲倒?jié)點(diǎn)。

c.若當(dāng)前節(jié)點(diǎn)不是最大（或最?。┲?，則與最大（或最?。┲倒?jié)點(diǎn)交換。

d.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)，重復(fù)b-c步驟，直到到達(dá)葉子節(jié)點(diǎn)。

（二）堆的插入操作

1.插入步驟

（1）將新元素添加到數(shù)組的末尾（保持完全二叉樹形狀）。

（2）通過上浮調(diào)整（BubbleUp）將新元素與父節(jié)點(diǎn)比較并交換，直到滿足堆特性。

（3）上浮調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為插入位置。

b.比較當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)，若不滿足堆特性則交換。

c.將當(dāng)前節(jié)點(diǎn)更新為被交換的父節(jié)點(diǎn)，重復(fù)a-b步驟，直到到達(dá)根節(jié)點(diǎn)或滿足堆特性。

（三）堆的刪除操作

1.刪除步驟

（1）將根節(jié)點(diǎn)替換為數(shù)組的最后一個元素（保持完全二叉樹形狀）。

（2）通過下沉調(diào)整（BubbleDown）將根節(jié)點(diǎn)與子節(jié)點(diǎn)比較并交換，直到滿足堆特性。

（3）下沉調(diào)整步驟：

a.初始化當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)。

b.比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)，找到最大（或最?。┲倒?jié)點(diǎn)。

c.若當(dāng)前節(jié)點(diǎn)不是最大（或最小）值，則與最大（或最小）值節(jié)點(diǎn)交換。

d.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)，重復(fù)a-c步驟，直到到達(dá)葉子節(jié)點(diǎn)或滿足堆特性。

三、堆調(diào)整的效率分析

（一）時(shí)間復(fù)雜度

1.從無序數(shù)組構(gòu)建堆：

-自底向上調(diào)整：O(n)，其中n為節(jié)點(diǎn)數(shù)量。

-自頂向下調(diào)整：O(nlogn)，效率較低。

2.插入操作：O(logn)，需上浮調(diào)整。

3.刪除操作：O(logn)，需下沉調(diào)整。

（二）空間復(fù)雜度

1.所有操作均原地修改數(shù)組，空間復(fù)雜度為O(1)。

四、應(yīng)用場景

1.優(yōu)先隊(duì)列實(shí)現(xiàn)。

2.堆排序算法的基礎(chǔ)。

3.貪心算法中的狀態(tài)管理。

4.圖算法中的最小/最大生成樹計(jì)算。

一、堆的基本概念

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常用數(shù)組實(shí)現(xiàn)。堆具有以下關(guān)鍵特性：

（一）堆形狀特性

1.堆必須是一棵完全二叉樹。

-完全二叉樹的定義：除最后一層外，每一層都是滿的，且最后一層節(jié)點(diǎn)從左到右連續(xù)排列。

-數(shù)組表示法中，節(jié)點(diǎn)的索引與其子節(jié)點(diǎn)索引存在固定關(guān)系，便于快速訪問。

-對于索引為i的節(jié)點(diǎn)：

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

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

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

（二）堆值特性

1.最大堆（MaxHeap）：父節(jié)點(diǎn)值始終大于或等于子節(jié)點(diǎn)值。

-應(yīng)用場景：快速獲取最大值。

-示例：在數(shù)組中，根節(jié)點(diǎn)（索引0）存儲最大值。

2.最小堆（MinHeap）：父節(jié)點(diǎn)值始終小于或等于子節(jié)點(diǎn)值。

-應(yīng)用場景：快速獲取最小值。

-示例：在數(shù)組中，根節(jié)點(diǎn)（索引0）存儲最小值。

三、堆的調(diào)整規(guī)則

堆的調(diào)整是指將一個無序的數(shù)組重新排列成符合堆特性的結(jié)構(gòu)。調(diào)整分為兩種場景：

（一）從無序數(shù)組構(gòu)建堆

1.自底向上調(diào)整（Bottom-UpHeapify）

-適用于從空堆逐步添加元素，或從完全二叉樹的葉子節(jié)點(diǎn)向上構(gòu)建堆。

-優(yōu)勢：時(shí)間復(fù)雜度為O(n)，效率較高。

-具體步驟：

（1）確定起始調(diào)整節(jié)點(diǎn)：

-從最后一個非葉子節(jié)點(diǎn)開始調(diào)整。

-非葉子節(jié)點(diǎn)計(jì)算公式：`start_index=(n-2)/2`，其中n為數(shù)組長度。

（2）逐個節(jié)點(diǎn)向上調(diào)整：

-從`start_index`開始，依次向上遍歷至根節(jié)點(diǎn)（索引0）。

-對于每個節(jié)點(diǎn)i：

a.比較與交換：

-比較節(jié)點(diǎn)i與其左右子節(jié)點(diǎn)（`2i+1`和`2i+2`）。

-找出三個節(jié)點(diǎn)中的最大值（在最大堆中），或最小值（在最小堆中）。

-若節(jié)點(diǎn)i不是最大/最小值，則與最大/最小子節(jié)點(diǎn)交換。

b.更新當(dāng)前節(jié)點(diǎn)：

-將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)（交換后子節(jié)點(diǎn)可能不再滿足堆特性）。

-重復(fù)比較與交換，直到節(jié)點(diǎn)i為葉子節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)遍歷至根節(jié)點(diǎn)且所有節(jié)點(diǎn)均滿足堆特性時(shí)，構(gòu)建完成。

2.自頂向下調(diào)整（Top-DownHeapify）

-適用于從有序數(shù)組轉(zhuǎn)換為堆，或刪除根節(jié)點(diǎn)后重新調(diào)整。

-優(yōu)勢：代碼實(shí)現(xiàn)簡單，但時(shí)間復(fù)雜度為O(nlogn)，效率較低。

-具體步驟：

（1）初始化當(dāng)前節(jié)點(diǎn)：

-從根節(jié)點(diǎn)（索引0）開始。

（2）逐個節(jié)點(diǎn)向下調(diào)整：

-對于每個節(jié)點(diǎn)i：

a.比較與交換：

-比較節(jié)點(diǎn)i與其左右子節(jié)點(diǎn)。

-找出最大/最小子節(jié)點(diǎn)。

-若節(jié)點(diǎn)i不是最大/最小值，則與最大/最小子節(jié)點(diǎn)交換。

b.更新當(dāng)前節(jié)點(diǎn)：

-將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)。

-重復(fù)比較與交換，直到當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)遍歷至最后一個葉子節(jié)點(diǎn)且所有節(jié)點(diǎn)均滿足堆特性時(shí)，調(diào)整完成。

（二）堆的插入操作

1.插入步驟

-目標(biāo)：將一個新元素添加到堆中，并保持堆特性。

-具體步驟：

（1）添加元素：

-將新元素添加到數(shù)組的末尾（保持完全二叉樹形狀）。

-例如，在最大堆中，新元素初始值可能小于根節(jié)點(diǎn)，需要調(diào)整。

（2）上浮調(diào)整（BubbleUp）：

-初始化當(dāng)前節(jié)點(diǎn)為插入位置（數(shù)組末尾）。

-比較當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)：

a.若當(dāng)前節(jié)點(diǎn)值大于父節(jié)點(diǎn)值（最大堆），或小于父節(jié)點(diǎn)值（最小堆），則交換。

b.若不滿足交換條件，則停止調(diào)整。

-將當(dāng)前節(jié)點(diǎn)更新為被交換的父節(jié)點(diǎn)，重復(fù)比較與交換，直到到達(dá)根節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，或父節(jié)點(diǎn)值大于/小于當(dāng)前節(jié)點(diǎn)值時(shí)，插入完成。

（三）堆的刪除操作

1.刪除步驟

-目標(biāo)：刪除堆頂元素（根節(jié)點(diǎn)），并保持堆特性。

-具體步驟：

（1）替換根節(jié)點(diǎn)：

-將數(shù)組的最后一個元素移動到根節(jié)點(diǎn)位置（覆蓋原根節(jié)點(diǎn)）。

-數(shù)組長度減1，保持完全二叉樹形狀。

（2）下沉調(diào)整（BubbleDown）：

-初始化當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)。

-比較當(dāng)前節(jié)點(diǎn)與左右子節(jié)點(diǎn)：

a.找出最大/最小子節(jié)點(diǎn)。

b.若當(dāng)前節(jié)點(diǎn)不是最大/最小值，則與最大/最小子節(jié)點(diǎn)交換。

c.將當(dāng)前節(jié)點(diǎn)更新為被交換的子節(jié)點(diǎn)。

-重復(fù)比較與交換，直到當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)或滿足堆特性。

（3）終止條件：

-當(dāng)當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，或左右子節(jié)點(diǎn)不存在（即無子節(jié)點(diǎn)），下沉調(diào)整完成。

三、堆調(diào)整的效率分析

（一）時(shí)間復(fù)雜度

1.從無序數(shù)組構(gòu)建堆：

-自底向上調(diào)整：O(n)，可通過數(shù)學(xué)證明優(yōu)化。

-自頂向下調(diào)整：O(nlogn)，適用于少量節(jié)點(diǎn)調(diào)整。

2.插入操作：O(logn)，需上浮調(diào)整。

3.刪除操作：O(logn)，需下沉調(diào)整。

（二）空間復(fù)雜度

1.所有操作均原地修改數(shù)組，空間復(fù)雜度為O(1)。

四、堆調(diào)整的優(yōu)化技巧

（一）減少比較次數(shù)

1.提前終止：

-在上浮/下沉調(diào)整中，若交換后父節(jié)點(diǎn)/子節(jié)點(diǎn)值相等，可提前終止。

2.懶惰比較：

-記錄最后一次交換的位置，后續(xù)調(diào)整僅在該位置以下進(jìn)行比較。

（二）避免重復(fù)計(jì)算

1.緩存子節(jié)點(diǎn)值：

-在下沉調(diào)整中，可先計(jì)算左右子節(jié)點(diǎn)值，再進(jìn)行比較，避免多次訪問子節(jié)點(diǎn)。

2.索引偏移：

-對于固定大小的數(shù)組，可預(yù)計(jì)算父/子節(jié)點(diǎn)索引偏移量，減少除法運(yùn)算。

（三）并行化處理

1.分塊調(diào)整：

-將堆劃分為多個區(qū)塊，并行執(zhí)行上浮/下