數據結構與算法：堆

朋友們大家好啊，本篇文章來到堆的內容，堆是一種完全二叉樹，再介紹堆之前，我們首先對樹進行講解

樹與堆

1.樹的介紹
- 1.1節點的分類
2.樹的存儲結構
3.二叉樹的概念和結構
- 3.1 二叉樹的特點
- 3.2 特殊的二叉樹
- 3.3二叉樹的存儲結構
4.堆的介紹和實現
- 4.1 堆的實現，初始化與銷毀
- 4.2插入元素與向上調整
- - 4.2.1堆向上調整
  - 4.2.2堆的建立
  - 4.2.3 堆元素的刪除和向下調整
- 4.3 獲取堆頂元素與堆的數據個數
- 4.4判斷堆是否為空

1.樹的介紹

在這里插入圖片描述

樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，n=0時成為空樹，當n>1時,其余結點可分為m(m>0)個互不相交的有限集T1、T2、……、Tm,其中每一個集合本身又是一棵樹,并且稱為根的子樹(SubTree)。

有一個特殊的結點，稱為根結點（A），根節點沒有前驅結點。n>0 時根結點是唯一的，不可能存在多個根節點
每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構
在這里插入圖片描述
這兩種情況就是錯誤的

1.1節點的分類

樹的結點包含一個數據元素及若干指向其子樹的分支。結點擁有的子樹數稱為結點的度(Degree)。度為0的結點稱為葉結點(Leaf)或終端結點度不為0的結點稱為非終端結點或分支結點。除根結點之外，分支結點也稱為內部結點。樹的度是樹內各結點的度的最大值。如圖所示，這棵樹結點的度的最大值是結點D的度為3，所以樹的度為3
在這里插入圖片描述

結點的子樹的根稱為該結點的孩子，相應地，該結點稱為孩子的雙親同一個雙親的孩子之間互稱兄弟。結點的祖先是從根到該結點所經分支上的所有結點。

在這里插入圖片描述
結點的層次（Level)從根開始定義起，根為第一層，根的孩子為第二層。若某結點在第L層，則其子樹的根就在第L+1層。其雙親在同一層的結點互為堂兄弟。顯然 D、E、F是堂兄弟。樹中結點的最大層次稱為樹的深度(Depth)或高度，當前樹的深度為4。

2.樹的存儲結構

提到存儲結構，我們會想到兩種：順序存儲和鏈式存儲
先來看看順序存儲結構，用一段地址連續的存儲單元依次存儲線性表的數據元素。這對于線性表來說是很自然的

樹中某個結點的孩子可以有多個，這就意味著，無論按何種順序將樹中所有結點存儲到數組中，結點的存儲位置都無法直接反映邏輯關系，你想想看，數據元素挨個的存儲，誰是誰的雙親，誰是誰的孩子呢?簡單的順序存儲結構是不能滿足樹的實現要求的。

樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法

任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們設置兩個指針，分別指向該結點的第一個孩子和此結點的右兄弟。

其中data是數據域，firstchild為指針域，存儲該結點的第一個孩子結點的存儲地址,rightsib是指針域，存儲該結點的右兄弟結點的存儲地址。

typedef int DataType;
struct Node
{struct Node* firstchild; // 第一個孩子結點struct Node* rightsib; // 指向其下一個兄弟結點DataType data; // 結點中的數據域
};

在這里插入圖片描述

3.二叉樹的概念和結構

二叉樹(Binary Tree)是n(n≥0)個結點的有限集合,該集合或者為空集(稱為空二叉樹),或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

3.1 二叉樹的特點

每個結點最多有兩棵子樹，所以二叉樹中不存在度大于2的結點。注意不是只有兩棵子樹，而是最多有。沒有子樹或者有一棵子樹都是可以的。
左子樹和右子樹是有順序的，次序不能任意顛倒。
即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。

二叉樹具有五種基本情況：
在這里插入圖片描述

3.2 特殊的二叉樹

在這里插入圖片描述

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。一個樹的層數為K，且節點總數為2^k-1，則它就是滿二叉樹
單是每個結點都存在左右子樹，不能算是滿二叉樹，還必須要所有的葉子都在同一層上，這就做到了整棵樹的平衡。
完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。

完全二叉樹的特點：

(1)葉子結點只能出現在最下兩層。
(2)最下層的葉子一定集中在左部連續位置。
(3)倒數二層，若有葉子結點，一定都在右部連續位置
(4)如果結點度為1，則該結點只有左孩子，即不存在只有右子樹的情況
(5)同樣結點數的二叉樹,完全二叉樹的深度最小

完全二叉樹的性質

若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 2^i-1 個結點
若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 2^h-1
對任何一棵二叉樹, 如果度為0其葉結點個數為n₀，度為2的分支結點個數為n₂，則有n₀＝n₂＋1
具有n個節點的完全二叉樹的深度為[log₂n]+1

對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編號，則對于序號為i的結點有：
5. 若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
6. 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
7. 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

3.3二叉樹的存儲結構

前面我們已經談到了樹的存儲結構，并且談到順序存儲對樹這種一對多的關系結構實現起來是比較困難的。但是二叉樹是一種特殊的樹，由于它的特殊性，使得用順序存儲結構也可以實現。
二叉樹的順序存儲結構就是用一維數組存儲二叉樹中的結點，并且結點的存儲位置，也就是數組的下標要能體現結點之間的邏輯關系，比如雙親與孩子的關系，左右兄弟的關系等
在這里插入圖片描述
將這棵二叉樹存入到數組中,相應的下標對應其同樣的位置

考慮一種極端的情況，一棵深度為k的右斜樹，它只有k個結點，卻需要分配2^k一1個存儲單元空間，這顯然是對存儲空間的浪費，如圖:

所以，順序存儲結構一般只用于完全二叉樹

4.堆的介紹和實現

堆是一棵完全二叉樹，堆中的每一個節點都滿足堆性質，也就是每個節點的值都必須大于（或等于）或小于（或等于）其子節點的值。根據這個性質，堆可以分為兩種類型：

大堆：在大堆中，每個父節點的值都大于或等于其子節點的值。因此，堆的根節點（即堆頂）包含了堆中的最大值。
小堆：在小堆中，每個父節點的值都小于或等于其子節點的值。因此，堆的根節點包含了堆中的最小值。

下面是一個小堆的結構：

       1/   \3     6/ \   / \5  9  8   13

在這個小堆中：

根節點1是最小的元素。
每個子節點3, 6的值都大于等于它們的父節點1的值。
這個性質適用于堆的所有層：例如，節點5, 9, 8, 13的值都大于等于它們各自的父節點3, 6的值。

這個小堆對應數組存儲結構為1 3 6 5 9 8 13

下面是一個大堆的結構：

       13/    \9      8/ \    / \5  3   6   1

對應數組結構為13 9 8 5 3 6 1

堆的樹形結構只是一種抽象的概念，在實際的物理存儲上，堆通常是以數組的形式來實現的

4.1 堆的實現，初始化與銷毀

堆的成立是數組數據不斷調整的過程，這里我們創建出堆的框架：

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;

初始化

void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

初始化堆數據數組的指針為 NULL。這意味著堆開始時沒有分配任何內存用于存儲元素。通常，在第一次向堆中添加元素時，程序會根據需要分配內存

銷毀

void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->size = 0;php->capacity = 0;
}

free 函數釋放堆結構中動態分配的數組 a 所占用的內存。php->a 是指向堆中元素數組的指針，在堆初始化或元素添加過程中，會通過 malloc、realloc 等動態內存分配函數分配內存。釋放這塊內存是防止內存泄露的重要步驟。釋放后，這塊內存不應再被訪問

4.2插入元素與向上調整

void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->capacity = newcapacity;php->a = tmp;}php->a[php->size] = x;php->size++;Ajustup(php->a, php->size - 1);
}

首先判斷php不為空，再進行擴容，這個擴容在前面有多次提到
最主要的是下面的Ajustup函數

4.2.1堆向上調整

我們這里以小堆為例進行講解：

當向堆中插入一個新元素后，為了維持小頂堆的性質（即父節點的值始終小于等于其子節點的值），可能需要進行元素的向上調整）。下面詳細說明這個過程：

當一個新元素被加入到堆中時，它首先被放置在堆的末尾（即作為樹的最底層的最右側的葉子節點），以保持完全二叉樹的形狀。
比較新節點與其父節點的值：插入的新元素可能會破壞小頂堆的性質，此時需要將新元素與其父節點進行比較。對于數組中的節點 i（假設索引從0開始），其父節點的位置是 (i - 1) / 2。注意這里全是整數值，比如下標為2的元素，它的父節點就為0
如果新元素的值小于其父節點的值，那么就需要交換這兩個節點的值，因為在小頂堆中父節點應當是小于或等于子節點的值
向上遞歸：繼續將現在的節點位置（原父節點的位置，因為已經交換）與新的父節點進行比較，如果還是小新的父節點的值，繼續交換。這一過程一直進行，直到新元素到達根節點，或新元素大于或等于其父節點的值。

在這里插入圖片描述
接下來我們用函數實現

void Ajustup(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}elsebreak;}
}

對于給定的子節點索引child，其父節點的索引計算為(child - 1) / 2
循環條件：while (child > 0)循環確保我們不會嘗試移動根節點（因為根節點的索引為0，沒有父節點）。循環繼續執行，只要當前節點的索引大于0。
完成交換后，更新child變量為原父節點的索引，因為交換后當前元素已經移動到了父節點的位置。然后，對新的child值重新計算parent索引，繼紺執行可能的進一步交換
循環終止條件：如果當前節點的值不小于其父節點的值（即堆的性質得到了滿足），循環終止，else break;執行

補充Swap函數：

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2; *p2 = tmp;
}

有了這個調整函數，我們就可以建堆了

4.2.2堆的建立

通過調用Ajustup函數，逐步把輸入數組a轉換成一個小堆

我們在主函數中進行測試
在這里插入圖片描述

在這里插入圖片描述
這個經驗證確實是一個小堆

4.2.3 堆元素的刪除和向下調整

堆默認規定，要刪除根節點的數據

堆頂存放最小值，刪除后，為了滿足小堆的性質，接下來根節點存儲的為次小值

由于堆是以數組的形式存儲的，堆頂元素就是數組的第一個元素。刪除堆頂元素后，需要保持堆的完整性和順序特性
將堆的最后一個元素移動到堆頂：為了保持結構性質，堆的最后一個元素被移動到堆頂位置。這是因為在二叉堆中，我們希望維護一個完全二叉樹的結構。使用最后一個元素來替代被刪除的元素是一種簡單且有效的方法，它保證了樹的結構完整性。
移動最后一個元素到堆頂后，這個新的堆頂元素可能會破壞堆的順序性質。為了恢復堆的性質，需要執行下沉操作。具體步驟如下：
- 比較新的堆頂元素與其子節點。
- 如果在最小堆中，新的堆頂元素比其子節點大，則它需要與其最小的子節點交換位置；在最大堆中，如果新的堆頂元素比其子節點小，則它需要與其最大的子節點交換位置。
- 重復這個比較和交換過程，直至新的堆頂元素被移至正確的位置，也就是說，它不再比任何一個子節點大（在最小堆中）或小（在最大堆中）

void HeapPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;Ajustdown(php->a,php->size,0);
}

在這里插入圖片描述
向下調整函數

void Ajustdown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child<size){if (child + 1 < size && a[child + 1] < a[child])//防止只有左孩子而越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}

我們需要找小一點的孩子進行交換

子節點選擇：計算左子節點的索引（child = parent * 2 + 1）。在二叉堆中，給定父節點索引為i的情況下，左子節點的索引為2*i + 1，右子節點的索引為2*i + 2。開始時，我們先考慮左子節點。
while循環：確保當前考慮的子節點索引沒有超出數組的界限，如果有兩個節點，判斷右節點是否小于左節點，如果小，child++，后面讓右孩子與父節點交換
更新parent索引為當前child的索引，繼續向下遍歷堆。更新child索引為新parent索引的左子節點，準備進行下一輪的比較。
結束循環：如果子節點的值不小于父節點的值，說明當前父節點的位置適當，堆的性質得以維持，此時循環可以終止。

對于每次AdjustDown調用，最壞情況下需要進行的比較和交換次數與堆的高度成正比，即O(log n)

AdjustDown操作的時間復雜度是O(log n)

4.3 獲取堆頂元素與堆的數據個數

HPDataType HeapTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

int HeapSize(Heap* php)
{assert(php);return php->size;
}

4.4判斷堆是否為空

bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

如果是空，返回true，不是則返回false

本節內容到此結束，感謝大家觀看！！！