[數據結構——lesson10.堆及堆的調整算法]

引言

上節我們學習完二叉樹后[數據結構——lesson9.二叉樹]，這節我們將學習數據結構——堆

學習目標

1.堆的概念及結構

堆是一種特殊的完全二叉樹結構，在計算機科學和數據結構中廣泛應用，特別是在堆排序算法和優先隊列的實現中，堆可以通過數組來表示，這種表示方式利用了完全二叉樹的性質，即除了最后一層外，每一層都被完全填滿，并且所有節點都盡可能地向左對齊。

1.1堆的概念

堆通常是一個可以被看作一棵完全二叉樹的數組對象，若滿足：

(1)任意節點的值>=其子節點的值。則稱為大根堆。

(2)任意節點的值<=其子節點的值。則稱為小根堆。

1.2堆的結構

邏輯結構：堆是一棵完全二叉樹，除了最后一層外，每一層都被完全填滿，并且所有節點都盡可能地向左對齊。
物理結構：堆在物理上通常采用順序存儲，即使用數組來表示。根節點位于數組的第一個位置（下標通常為 0 或 1）。對于下標從 1 開始的數組，任意節點 i 的左子節點為 2i，右子節點為 2i+1；對于下標從 0 開始的數組，左子節點為 2i+1，右子節點為 2i+2。通過這種方式，可以利用數組的隨機訪問特性高效地模擬樹的結構。

如圖所示：

?操作系統和數據結構這兩門學科中都有棧和堆的概念，如何區分 ?

數據結構角度

棧：是一種運算受限的線性表2。只允許在表的一端進行插入和刪除操作，遵循后進先出（LIFO）原則。主要操作有入棧（Push）和出棧（Pop）。可使用數組或鏈表作為底層數據結構，分別稱為順序棧和鏈式棧。
堆：是一種特殊的樹形數據結構。通常可分為最大堆和最小堆，最大堆中父節點的值大于等于子節點的值，最小堆中父節點的值小于等于子節點的值。主要操作包括插入元素和刪除堆頂元素等，并需重新調整堆的結構。常用于實現優先隊列、堆排序等。

操作系統角度

棧：是進程地址空間中的一塊區域，用于存儲函數調用時的局部變量、函數參數和返回地址等信息。其內存由操作系統自動分配和釋放，函數調用時壓棧，函數返回時彈棧。棧的大小有限，一般每個進程的棧大小相對較小，如 64 位 Linux 系統默認棧大小通常為 10MB。內存地址生長方向是從高地址向低地址增長。
堆：也是進程地址空間中的一部分，用于動態內存分配。程序運行時通過 malloc 或 new 等函數分配內存，大小可變。內存由程序員手動管理，需調用相應函數釋放內存，否則易引發內存泄漏。堆的內存地址通常從低地址向高地址增長，由于是通過分散的內存塊管理，其內存空間在物理上不連續，頻繁操作可能產生內存碎片。

二者聯系

1.3堆的調整算法

在實現堆的結構之前我們先要了解一下堆的調整算法

1.堆的數值交換

思路：堆的交換還是比較簡單的，跟之前寫的沒什么區別，記得傳地址。
void swap(HPDatatype* x, HPDatatype* y)
{int temp = 0;temp = *x;*x = *y;*y = temp;
}
2.堆的向上調整算法?（應用于堆的數據插入）

此算法是為了確保插入數據后的堆依然是符合堆的性質而單獨封裝出來的函數，就好比如我們后續要插入的數字10（小堆）

基本思路：將新增元素插入到堆數組的末尾，然后將該元素與其父結點進行比較。若該元素的值小于父結點的值（小根堆）或大于父結點的值（大根堆），則交換兩者的位置，之后將原父結點當作新的目標結點，繼續向上進行比較和交換操作，直到該元素的值不小于父結點的值（小根堆）或不大于父結點的值（大根堆），或者到達根節點為止。

為了確保在插入數字10后依然是個小根堆，所以要將10和28交換，依次比較父結點parent和子結點child的大小，當父小于子結點的時候，就返回，反之就一直交換，直到根部while(child>0)截止。

：由前文的得知的規律，parent = (child - 1) / 2，我們操控的是數組，但要把它想象成二叉樹。畫圖演示調整過程：

代碼實現：
// 向上調整函數（沒有改變動態數組的首地址，不需要用指針傳輸）
// 時間復雜度O(logN)
// 傳入了 動態數組  和  最后一個位置的下標（也就是孩子的下標）
// 向上調整的條件；上面的數據是堆
void AdjustUp(HPDatatype* a, int child)
{// 計算父親的小標int parent = (child - 1) / 2;// 當 child 的小標大于 0 就繼續 （也就小于是根節點位置）while (child > 0){// 小堆 <// 大堆 >if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
核心邏輯：

計算父節點下標：parent = (child - 1) / 2
循環比較子節點與父節點的值
如果子節點值小于父節點值（符合小堆特性），則交換兩者位置
更新子節點和父節點下標，繼續向上比較
當子節點成為根節點（child > 0不成立）或滿足堆特性時，循環結束

3.堆的向下調整算法（應用于堆的數據刪除）

此算法是為了確保刪除數據后的堆依然是符合堆的性質而單獨封裝出來的函數，就好比如我們后續要刪除數字10（小堆）

基本思路：首先將堆頂元素與堆中最后一個元素進行交換，然后刪除最后一個元素（此時堆頂元素為原來的堆尾元素）。接著從堆頂開始，將堆頂元素與它的子節點進行比較，如果子節點中有比它更小（小根堆）或更大（大根堆）的元素，則將堆頂元素與該子節點交換位置，之后繼續以交換后的位置為新的 “堆頂”，重復上述比較和交換操作，直到滿足堆的性質為止。

如下圖：

（我們這里首先將堆頂元素（10）與堆中最后一個元素進行交換（28），然后刪除最后一個元素（10））

此時我們看到，這個二叉樹整體上不符合堆的性質，但是其根部的左子樹和右子樹均滿足堆的性質。?接下來，就要進行向下調整，確保其最終是個堆。只需三部曲。

?：找出左右孩子中最小的那個

?：跟父親比較，如果比父親小，就交換

?：再從交換的孩子位置繼續往下調整

代碼實現：
// 向下調整
// 向下調整的前提：后面的數據是堆
void AdjustDown(HPDatatype* a, int n, int parent)
{// 左孩子int child = parent * 2 + 1;// 孩子可能會超出數組范圍while (child < n){// 如果右孩子小于左孩子// 找出小的那個孩子// 保證右孩子存在且不越界// 大堆 >// 小堆 <if (child + 1 < n && a[child+1] < a[child]){//跳轉到有孩子那里child++;}// 開始向下調整// 大堆 >// 小堆 <if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
核心邏輯：

先計算左孩子下標：child = parent * 2 + 1
循環條件：孩子下標小于總元素個數（未超出邊界）
首先判斷是否存在右孩子，并且比較左右孩子大小，選擇較小的那個孩子（小堆特性）
比較父節點與選中的孩子節點值，如果孩子值更小，則交換兩者位置
更新父節點和孩子節點下標，繼續向下比較
當父節點滿足堆特性或沒有孩子節點時，循環結束

2.堆的實現方式

雖然堆是一種特殊的二叉樹，它既可以用數組存儲也可以用鏈式存儲。但是考慮到其完全二叉樹的特性，我們在這里采用數組存儲的方式，因為這樣既方便訪問，也并不會浪費格外的空間。

數組與堆的映射關系(這里實現根的下標為0)：

1.若某節點在數組中的下標為i（i從0開始），則其左子節點(若存在)的下標為2i+1，右子節點（若存在）的下標為2i+2，其父節點（若存在）的下標為（i-1）/2。

2.堆的根節點在數組的下標為0。

2.1堆的聲明

由于我們使用數組來實現堆，因此堆的聲明與順序表類似。