目錄

一、樹概念及結(jié)構(gòu)

二、二叉樹樹概念及結(jié)構(gòu)

?特殊的二叉樹

三、堆的概念及結(jié)構(gòu)

四、堆的創(chuàng)建

1、聲明結(jié)構(gòu)體

2、初始化?

3、銷毀

4、添加新元素

5、交換元素?

6、向上調(diào)整

7、判斷堆是否為空

8、移除堆頂元素

9、向下調(diào)整

10、獲取堆元素個數(shù)?

五、使用堆排序

?排降序建小堆

?完整版：

Heap.h聲明部分

Heap.c函數(shù)部分

text.c使用及測試部分

---

一、樹概念及結(jié)構(gòu)

• 節(jié)點(diǎn)的度：一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6
• 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I...等節(jié)點(diǎn)為葉節(jié)點(diǎn)
• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G...等節(jié)點(diǎn)為分支節(jié)點(diǎn)
• 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
• 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)
• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)
• 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6
• 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4
• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)
• 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
• 森林：由m（m>0）棵互不相交的樹的集合稱為森林；

二、二叉樹樹概念及結(jié)構(gòu)

二叉樹是一個由n(n>=0)個結(jié)點(diǎn)構(gòu)成的有限集合，其中該集合可以為空，這時稱其為空二叉樹；或者由一個根結(jié)點(diǎn)以及兩個互不相交的左子樹和右子樹組成，且左右子樹均為二叉樹。在二叉樹中，子樹被明確區(qū)分為左子樹和右子樹，且它們的順序不可顛倒。

• 值得注意的是，二叉樹的定義具有遞歸性質(zhì)，因?yàn)槎鏄浔旧砜梢詾榭?#xff0c;根結(jié)點(diǎn)可以有空的左子樹或空的右子樹。
• 這使得二叉樹與普通樹有明顯的區(qū)別，即使只有一棵子樹存在，也需要明確指定它是左子樹還是右子樹。這是二叉樹與樹最主要的區(qū)別之一。
• 請注意，二叉樹不同于一般的樹，因?yàn)樗淖訕渚哂凶笥抑?#xff0c;并且順序不能顛倒。因此，“二叉樹是結(jié)點(diǎn)度為2的樹”的說法是不正確的。

二叉樹的基本形態(tài)包括以下五種：

?特殊的二叉樹

當(dāng)涉及到二叉樹的特殊類型時，有兩個主要概念需要了解：滿二叉樹和完全二叉樹。

• 滿二叉樹：滿二叉樹是一種特殊的二叉樹，其特點(diǎn)是每個層級的結(jié)點(diǎn)數(shù)都達(dá)到最大值。具體來說，如果一個二叉樹的深度為K，且結(jié)點(diǎn)總數(shù)為2^K - 1，那么它就是一個滿二叉樹。滿二叉樹的每一層都包含最大數(shù)量的結(jié)點(diǎn)，使得它具有很特殊的結(jié)構(gòu)。
• 完全二叉樹：完全二叉樹是一種高效的數(shù)據(jù)結(jié)構(gòu)，與滿二叉樹相關(guān)。一個二叉樹如果在深度為K的情況下，其結(jié)點(diǎn)都與深度為K的滿二叉樹中的編號從1到n的結(jié)點(diǎn)一一對應(yīng)，那么它就被稱為完全二叉樹。需要注意的是，滿二叉樹是完全二叉樹的一個特殊情況。

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有個結(jié)點(diǎn)。
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是。
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個數(shù)為 n0?, 度為2的分支結(jié)點(diǎn)個數(shù)為 n2?,則有 n0 ＝n2?＋1。
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個結(jié)點(diǎn)的滿二叉樹的深度，h=log以2為底，n+1的對數(shù)。
5. 對于具有n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號，則對于序號為i的結(jié)點(diǎn)有：

• 若i>0，i位置節(jié)點(diǎn)的雙親序號：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號，無雙親節(jié)點(diǎn)
• 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
• 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

?

三、堆的概念及結(jié)構(gòu)

堆（Heap）是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)，通常用于實(shí)現(xiàn)優(yōu)先隊列和對數(shù)據(jù)進(jìn)行排序。堆的主要特點(diǎn)是它是一棵樹，其中每個節(jié)點(diǎn)的值滿足特定的堆屬性。在堆中，通常有兩種主要類型：最大堆和最小堆。

• 最大堆（Max Heap）：在最大堆中，每個節(jié)點(diǎn)的值都不小于其子節(jié)點(diǎn)的值，即根節(jié)點(diǎn)的值最大。這意味著最大堆的最大元素總是位于根節(jié)點(diǎn)，而子樹中的值遞減。

• 最小堆（Min Heap）：在最小堆中，每個節(jié)點(diǎn)的值都不大于其子節(jié)點(diǎn)的值，即根節(jié)點(diǎn)的值最小。這意味著最小堆的最小元素總是位于根節(jié)點(diǎn)，而子樹中的值遞增。

堆的常見用途包括：

• 優(yōu)先隊列：堆可以用來實(shí)現(xiàn)高效的優(yōu)先隊列，使得可以快速訪問和刪除具有最高或最低優(yōu)先級的元素。

• 堆排序：堆排序是一種高效的排序算法，它利用堆的性質(zhì)來進(jìn)行排序。它的時間復(fù)雜度為O(n log n)。

堆通常是以數(shù)組的形式來表示，其中父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的關(guān)系通過數(shù)組索引來建立。具體來說，對于一個具有n個元素的堆，節(jié)點(diǎn)的索引從1到n編號，其中：

• 父節(jié)點(diǎn)的索引為i，則它的左子節(jié)點(diǎn)的索引為2i，右子節(jié)點(diǎn)的索引為2i + 1。
• 子節(jié)點(diǎn)的索引為i，則其父節(jié)點(diǎn)的索引為i/2。

這種數(shù)組表示方法使得堆的操作更加高效，因?yàn)樗恍枰褂妙~外的指針來表示樹的結(jié)構(gòu)。

四、堆的創(chuàng)建

本次以小堆舉例進(jìn)行講解?

1、聲明結(jié)構(gòu)體

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

• HPDataType?被定義為?int?類型，表示堆中存儲的數(shù)據(jù)類型。
• 創(chuàng)建堆的結(jié)構(gòu)體Heap，定義別名為HP。
• 指針a指向堆的數(shù)組
• size為堆的當(dāng)前大小
• capacity為堆的容量

2、初始化?

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

• assert 判斷指針是否合法。
• 指向數(shù)組的指針 a 初始化為 NULL。
• size 和 capacity 初始化為0。

3、銷毀

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

• assert 判斷指針是否合法。
• 釋放數(shù)組空間，將 a 指針置空，同時將 capacity 和 size 設(shè)置為0。

4、添加新元素

void HeapPush(HP* 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, newCapacity * sizeof(HPDataType));if (tmp==NULL) {perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

• assert 判斷指針是否合法。
• 判斷當(dāng)前是否需要擴(kuò)容，初始堆的容量為0，則為堆開辟四個HPDataType類型大小的空間，如果當(dāng)前堆的大小size等于容量capacity，則將堆擴(kuò)容為兩倍原來大小的空間。
• 擴(kuò)容失敗，打印錯誤信息，結(jié)束函數(shù)
• 將擴(kuò)容的空間賦值給指針a，更新容量capacity的大小。
• 將要增加的元素插入數(shù)組a中，更新size大小。
• 每次在堆中添加新元素時，小堆可能會被破壞，所以我們再添加新元素后，要在AdjustUp函數(shù)中判斷是否需要進(jìn)行向上調(diào)整。

5、交換元素?

后續(xù)函數(shù)會經(jīng)常用到，同一串代碼放到函數(shù)里供其使用者調(diào)用比較好。?

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

6、向上調(diào)整

void AdjustUp(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 = (child - 1) / 2;}else {break;}}
}

• 首先通過當(dāng)前的孩子節(jié)點(diǎn)child找到父節(jié)點(diǎn)parent。
• 當(dāng)child大于0時，進(jìn)行判斷當(dāng)前chilid是否需要調(diào)整
• 如果child位置元素小于parent位置元素，則通過Swap進(jìn)行交換，然后新的孩子節(jié)點(diǎn)更新為parent位置，通過孩子節(jié)點(diǎn)更新新的父節(jié)點(diǎn)位置，然后繼續(xù)比較和交換，直到不再需要交換為止。
• 如果當(dāng)前孩子節(jié)點(diǎn)不小于當(dāng)前的父節(jié)點(diǎn)，則結(jié)束循環(huán)，當(dāng)前節(jié)點(diǎn)不需要向上調(diào)整。

7、判斷堆是否為空

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

8、移除堆頂元素

?一般來說，堆的移除操作通常是移除堆頂元素，這樣大堆小堆的性質(zhì)保持不變，如果移除堆底會破壞堆的性質(zhì)。

void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

• assert 判斷指針是否合法。
• 檢查堆是否為空，為空則報錯。
• 移除堆頂元素有兩種方法，首選第二種方法，不需要重新建堆，節(jié)約時間。
• 
• 首先交換堆頂堆尾，然后size減一完成刪除，后續(xù)不會訪問刪除位置的元素，所以不釋放內(nèi)存空間也可以。
• 然后進(jìn)行向下調(diào)整。

9、向下調(diào)整

向下調(diào)整是從第一個節(jié)點(diǎn)（父節(jié)點(diǎn)）開始向下調(diào)整，傳入?yún)?shù)命名為parent?

void AdjustDown(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 = parent * 2 - 1;}else {break;}}
}

• 通過傳入?yún)?shù)獲取到當(dāng)前的左子節(jié)點(diǎn)的位置。
• 當(dāng)child位置小于數(shù)組元素個數(shù)時進(jìn)行判斷。
• 進(jìn)入循環(huán)，首先判斷檢查右子節(jié)點(diǎn)是否存在并且比左子節(jié)點(diǎn)的值小，如果是，將?child?更新為右子節(jié)點(diǎn)的索引，以確保選擇更小的子節(jié)點(diǎn)進(jìn)行比較。
• 比較選定的子節(jié)點(diǎn)的值與父節(jié)點(diǎn)的值，如果子節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值，就交換它們。
• 更新parent為新的子節(jié)點(diǎn)位置，更新child為新的左子節(jié)點(diǎn)位置，然后繼續(xù)比較和交換，直到不再需要交換為止。
• 如果當(dāng)前子節(jié)點(diǎn)不小于當(dāng)前父節(jié)點(diǎn)則停止循環(huán)。

10、獲取堆元素個數(shù)?

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

五、使用堆排序

void HeapSort(int* a, int n)
{HP hp;HeapInit(&hp);// 時間復(fù)雜度：N*logNfor (int i = 0; i < n; ++i){HeapPush(&hp, a[i]);}// 時間復(fù)雜度：N*logNint i = 0;while (!HeapEmpty(&hp)){int top = HeapTop(&hp);a[i++] = top;HeapPop(&hp);}HeapDestroy(&hp);
}

可以使用這種方式，但有諸多弊端：?

1. 要先有一個堆,太麻煩。
2. 空間復(fù)雜度+拷貝數(shù)據(jù)

?排降序建小堆

所以我們要在傳入的原數(shù)組上排降序，需要使用建小堆的方式向上調(diào)整。

void HeapSort(int* a, int n)
{// 建堆--向上調(diào)整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再調(diào)整，選出次小的數(shù)AdjustDown(a, end, 0);--end;}
}

• 從根節(jié)點(diǎn)的子節(jié)點(diǎn)開始向上建堆，除了根節(jié)點(diǎn)以外，每個節(jié)點(diǎn)都進(jìn)行向上調(diào)整。
• 定義堆的最后一個節(jié)點(diǎn)end為n-1
• 
• 我們將堆的根節(jié)點(diǎn)（也就是最小值）與堆的最后一個元素交換，即將最小值放到排序尾部即為好的部分。接下來，通過調(diào)用AdjustDown函數(shù)，將堆的大小減一，再次將堆調(diào)整為最小堆。
• 重復(fù)while循環(huán)內(nèi)部操作，直到整個數(shù)組排序完成。每次交換和堆的調(diào)整都會將最小的元素添加到已排序的部分，直到整個數(shù)組都有序。

HeapSort的時間復(fù)雜度為O(nlog(n))，它不需要額外的空間來存儲數(shù)據(jù)，所以是一種原地排序算法。它在最壞情況下的性能仍然是O(nlog(n))，因此相對穩(wěn)定，適用于大規(guī)模數(shù)據(jù)的排序。?

我們也可以向下建堆：

倒著調(diào)整葉子節(jié)點(diǎn)不需要處理，從倒樹第一個非葉子節(jié)點(diǎn)開始，即最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)開始調(diào)整。

void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){	AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再調(diào)整，選出次小的數(shù)AdjustDown(a, end, 0);--end;}
}

?完整版：

Heap.h聲明部分

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestroy(HP* php);void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* php, HPDataType x);
bool HeapEmpty(HP* php);
void AdjustDown(int* a, int n, int parent);
void HeapPop(HP* php);HPDataType HeapTop(HP* php);
int HeapSize(HP* php);

Heap.c函數(shù)部分

#include "Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(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 = (child - 1) / 2;}else {break;}}
}void HeapPush(HP* 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, newCapacity * sizeof(HPDataType));if (tmp==NULL) {perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}
void AdjustDown(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 = parent * 2 - 1;}else {break;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}

text.c使用及測試部分

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"void HeapSort(int* a, int n)
{// 建堆--向上調(diào)整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}// 建堆--向下調(diào)整建堆//for (int i = (n - 1 - 1) / 2; i >= 0; --i)//{//	AdjustDown(a, n, i);//}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再調(diào)整，選出次小的數(shù)AdjustDown(a, end, 0);--end;}		
}int main()
{int a[] = { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < 8; i++) {printf("%d  ", a[i]);}return 0;
}//---測試堆函數(shù)功能---
//int main()
//{
//	HP hp;
//	HeapInit(&hp);
//	int a[] = { 65,100,70,32,50,60 };
//	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
//	{
//		HeapPush(&hp, a[i]);
//	}
//	
//	while (!HeapEmpty(&hp))
//	{
//		int top = HeapTop(&hp);
//		printf("%d\n", top);
//		HeapPop(&hp);
//	}
//
//	return 0;
//}