? ? ? ?

目錄

一、二叉樹(shù)

1、二叉樹(shù)的概念

?2、完全二叉樹(shù)和滿二叉樹(shù)

3、完全二叉樹(shù)的順序存儲(chǔ)

二、堆

2、堆的概念與結(jié)構(gòu)

3、堆的創(chuàng)建及初始化

4、堆的插入（小堆）

?5、堆的刪除

6、顯示堆頂元素

7、顯示堆里的元素個(gè)數(shù)

8、測(cè)試堆的各個(gè)功能

9、 實(shí)現(xiàn)堆排序

三、TOP-K的實(shí)現(xiàn)

結(jié)語(yǔ)：

---

前言：

????????堆是數(shù)據(jù)結(jié)構(gòu)中是很重要的一個(gè)知識(shí)點(diǎn)，通常用于實(shí)現(xiàn)堆排序， 比如在生活中我們要算出考試成績(jī)的前十名，或者游戲排名的前一百名，這種場(chǎng)景下就用到堆排序了。堆其實(shí)是相同類型元素的集合，通常用數(shù)組的形式表示一個(gè)堆，數(shù)組內(nèi)的所有元素都按照完全二叉樹(shù)的形式進(jìn)行存儲(chǔ)，這時(shí)候又引出了二叉樹(shù)的概念，只要明白了完全二叉樹(shù)的概念就明白了什么是堆，因此下面先介紹二叉樹(shù)的基本概念。

一、二叉樹(shù)

1、二叉樹(shù)的概念

? ? ? ? 二叉樹(shù)的根節(jié)點(diǎn)由一個(gè)左子樹(shù)和一個(gè)右子樹(shù)構(gòu)成，也就是每一個(gè)結(jié)點(diǎn)可以少于兩個(gè)孩子結(jié)點(diǎn)但是不能多于兩個(gè)孩子結(jié)點(diǎn)，示意圖如下：

? ? ? ? 如上圖，D可以是A的孩子結(jié)點(diǎn)，同時(shí)D也可以是H的父母節(jié)點(diǎn)，D同時(shí)也是E的兄弟節(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)可以擁有多重身份。如果一棵樹(shù)中的任意一個(gè)結(jié)點(diǎn)有超過(guò)2個(gè)孩子結(jié)點(diǎn)那么該樹(shù)就不是一個(gè)二叉樹(shù)，二叉樹(shù)的其他情況如下：

?2、完全二叉樹(shù)和滿二叉樹(shù)

????????一顆二叉樹(shù)的每一層的結(jié)點(diǎn)都是滿的，將該二叉樹(shù)稱為滿二叉樹(shù)，完全二叉樹(shù)則是在滿二叉樹(shù)的概念上引申而來(lái)的，即滿二叉樹(shù)的最后一層的結(jié)點(diǎn)可以不是滿的，但是二叉樹(shù)中的所有結(jié)點(diǎn)從左到右必須是按照順序排序的，示意圖如下：

? ? ? ? ?因此可以看出完全二叉樹(shù)的一個(gè)特點(diǎn)：即每個(gè)節(jié)點(diǎn)必須是按照順序進(jìn)行存儲(chǔ)的，即完全二叉樹(shù)具有順序性。

3、完全二叉樹(shù)的順序存儲(chǔ)

????????我們知道數(shù)組是一塊連續(xù)的空間，而且數(shù)組里的元素都是“緊挨著”的，即不存在第一個(gè)元素和第三個(gè)元素中間空了位置不存儲(chǔ)任何數(shù)據(jù)，這么做不符合邏輯也很浪費(fèi)空間。由此看來(lái)，數(shù)組和完全二叉樹(shù)的特點(diǎn)非常相似。

? ? ? ? 因此一個(gè)完全二叉樹(shù)可以用數(shù)組的形式表示出來(lái)，只要是一個(gè)數(shù)組就是一個(gè)完全二叉樹(shù)。并且有了父母結(jié)點(diǎn)的下標(biāo)就可以找到他的孩子結(jié)點(diǎn)，有了孩子的結(jié)點(diǎn)就能找到其父母結(jié)點(diǎn)的下標(biāo)。?

? ? ? ? 比如有了結(jié)點(diǎn)B的下標(biāo)，可以找到他的左右兩個(gè)孩子結(jié)點(diǎn)的下標(biāo)：左孩子D的下標(biāo)=B的下標(biāo)*2+1，右孩子E的下標(biāo)=B的下標(biāo)*2+2。

? ? ? ? B的父母結(jié)點(diǎn)A坐標(biāo)=（B坐標(biāo)-1）/2。

二、堆

2、堆的概念與結(jié)構(gòu)

? ? ? ?堆是一個(gè)完全二叉樹(shù)，但是他在完全二叉樹(shù)的基本要求上增加了以下條件：樹(shù)里任意一個(gè)父母結(jié)點(diǎn)都大于等于（或小于等于）他們的孩子結(jié)點(diǎn)，因此堆分為兩種情況：大堆和小堆。

? ? ? ? 大堆：從根節(jié)點(diǎn)開(kāi)始，從上至下每個(gè)父親結(jié)點(diǎn)必須大于他的兩個(gè)孩子結(jié)點(diǎn)。

? ? ? ? 小堆：從根節(jié)點(diǎn)開(kāi)始，從上至下每個(gè)父親結(jié)點(diǎn)必須小于他的兩個(gè)孩子結(jié)點(diǎn)。

? ? ? ? 示意圖如下：

? ? ? ? 因此從以上的分析來(lái)看，可以得出以下結(jié)論：數(shù)組其實(shí)就可以看成是一個(gè)完全二叉樹(shù)，但是不一定是堆，但是是堆就一定是完全二叉樹(shù)。而且即使是小堆也不一定是升序，大堆也不一定是降序（這里只是偶然）。當(dāng)然，有序的數(shù)組一定是堆。?

? ? ? ? 接下來(lái)用代碼建立一個(gè)小堆。

3、堆的創(chuàng)建及初始化

? ? ? ? 從以上得知，堆的本質(zhì)是數(shù)組，因此堆的創(chuàng)建代碼如下：

typedef int HeapDataType;//int類型重定義
typedef struct Heap
{HeapDataType* arr;//指針arr，即數(shù)組名表示數(shù)組的首地址int size;//數(shù)組的元素個(gè)數(shù)int capacity;//數(shù)組的容量
}Heap;

?????????堆初始化代碼如下：

void HeapInit(Heap* php)//初始化
{assert(php);php->arr = NULL;//置為空php->size = 0;//剛開(kāi)始沒(méi)有元素因此為0php->capacity = 0;
}

4、堆的插入（小堆）

? ? ? ? 原理就是把數(shù)據(jù)插入到數(shù)組中，所以在數(shù)組的末尾處添加數(shù)據(jù)即可，但是單單的插入數(shù)據(jù)并不能滿足大堆和小堆的條件，因此每插入一個(gè)數(shù)據(jù)都要對(duì)數(shù)組進(jìn)行調(diào)整，以便然數(shù)組滿足小堆的條件。

? ? ? ? 然而從數(shù)組的末尾處插入元素，從完全二叉樹(shù)的角度來(lái)看，就是從樹(shù)的最后一個(gè)結(jié)點(diǎn)插入元素，因此對(duì)數(shù)組進(jìn)行調(diào)整其實(shí)就是調(diào)整插入元素與其父母結(jié)點(diǎn)的一個(gè)大小關(guān)系。插入最后一個(gè)結(jié)點(diǎn)的時(shí)候進(jìn)行對(duì)樹(shù)的調(diào)整的，該調(diào)整法稱為向上調(diào)整法。向上調(diào)整示意圖如下：

? ? ? ? 建小堆和向上調(diào)整法代碼如下：

void Swap(HeapDataType* p1, HeapDataType* p2)//交換函數(shù)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}void AdjustUp(HeapDataType* arr, int child)//向上調(diào)整函數(shù)
{assert(arr);int parent = (child - 1) / 2;//求出父母結(jié)點(diǎn)下標(biāo)while (child > 0)//等于0才結(jié)束循環(huán)說(shuō)明是最壞情況與根交換{if (arr[child] < arr[parent])//如果孩子小則與父母交換{Swap(&arr[child], &arr[parent]);//讓孩子結(jié)點(diǎn)和父母結(jié)點(diǎn)交換child = parent;//讓原先的父母結(jié)點(diǎn)變成孩子結(jié)點(diǎn)繼續(xù)調(diào)整parent = (child - 1) / 2;//找到原先父母結(jié)點(diǎn)的父母結(jié)點(diǎn)}else//表示沒(méi)有達(dá)到最壞情況{break;}}
}void HeapPush(Heap* php, HeapDataType x)//入堆
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;//三目法更新容量HeapDataType* temp = (HeapDataType*)realloc(php->arr, sizeof(HeapDataType) * newcapacity);//開(kāi)辟以及擴(kuò)容空間if (temp == NULL){perror("HeadFush");return;}php->arr = temp;//讓arr指向新的空間php->capacity = newcapacity;//更新容量}php->arr[php->size] = x;//入堆php->size++;//更新sizeAdjustUp(php->arr, php->size - 1);//向上調(diào)整堆
}

?5、堆的刪除

? ? ? ? 堆的刪除一般是將堆頂?shù)脑貏h除，堆頂?shù)脑丶词窍聵?biāo)為0的元素，也就是數(shù)組的第一個(gè)元素，如果將堆頂?shù)脑刂苯觿h除，堆肯定會(huì)發(fā)生變化，會(huì)導(dǎo)致該數(shù)組不再是堆了，因此進(jìn)行堆的刪除的同時(shí)要調(diào)整堆。因?yàn)槭嵌秧數(shù)脑匕l(fā)生了改變，所以從堆頂?shù)奈恢猛抡{(diào)整，進(jìn)行向下調(diào)整。向下調(diào)整堆的具體邏輯如下圖：

? ? ? ? 向下調(diào)整法思路：把堆頂元素和堆尾元素進(jìn)行交換，然后從堆頂處開(kāi)始向下調(diào)整，一直調(diào)整到元素30的前一個(gè)元素。讓堆頂元素跟他的兩個(gè)孩子中最小的孩子進(jìn)行比較，如果他的孩子比他小則他們倆進(jìn)行交換，如此循環(huán)往下比較，直到樹(shù)的最后一層。注意：此時(shí)的元素30是不參與調(diào)整的。

? ? ? ? 堆的刪除及向下調(diào)整法代碼如下：?

bool Empty(Heap* php)//判空函數(shù)
{assert(php);return php->size == 0;//為空即返回真
}void AdjustDown(HeapDataType* arr, int size, int parent)//向下調(diào)整堆
{assert(arr);int child = parent * 2 + 1;//找出其左孩子while (child < size)//若孩子的下標(biāo)已經(jīng)超出了數(shù)組元素個(gè)數(shù)，說(shuō)明數(shù)組已經(jīng)是堆{if ((child + 1 < size) && arr[child + 1] < arr[child])//此判斷可以找出最小的孩子{child++;}if (arr[child] < arr[parent])//若孩子小于父母則交換{Swap(&arr[child], &arr[parent]);parent = child;//進(jìn)行往下遍歷child = parent * 2 + 1;}else{break;}}
}void HeapPop(Heap* php)//刪除堆頂
{assert(php);assert(!Empty(php));//堆為空則Empty函數(shù)返回真，對(duì)其取非，則堆為空assert生效Swap(&php->arr[0], &php->arr[php->size - 1]);//交換函數(shù)php->size--;szie需要--因?yàn)榇藭r(shí)的size是最后一個(gè)元素的后一個(gè)位置AdjustDown(php->arr, php->size, 0);//向下調(diào)整堆，從堆頂開(kāi)始到堆尾結(jié)束
}

6、顯示堆頂元素

? ? ? ? 顯示堆頂元素就很簡(jiǎn)單了，堆頂表示的是數(shù)組的首元素，首元素下標(biāo)為0，顯示堆頂代碼如下：

HeapDataType HeapTop(Heap* php)//展示堆頂
{assert(php);return php->arr[0];
}

7、顯示堆里的元素個(gè)數(shù)

? ? ? ? 堆的大小就是size的值，因?yàn)槊看钨x值后size都會(huì)++，所以剛好可以用size表示元素個(gè)數(shù)，代碼如下：

int HeapSize(Heap* php)//堆的元素的總數(shù)
{assert(php);return php->size;
}

8、測(cè)試堆的各個(gè)功能

? ? ? ?以上介紹了那么多的功能，現(xiàn)在對(duì)這些功能進(jìn)行測(cè)試，代碼如下：

void test1()
{Heap hp;//創(chuàng)建堆的結(jié)構(gòu)體變量HeapInit(&hp);//初始化int a[] = { 7,8,3,5,1,9,4,5 };for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);//把數(shù)組a里的元素入進(jìn)堆里}printf("size:%d\n", HeapSize(&hp));//打印堆里元素總數(shù)int i = 0;while (!Empty(&hp))//循環(huán)打印出堆里的所有元素{printf("%d ",HeapTop(&hp));//打印堆頂?shù)脑豀eapPop(&hp);//刪除堆頂元素}HeapDestroy(&hp);//釋放堆
}int main()
{test1();return 0;}

? ? ? ? 運(yùn)行結(jié)果：

? ? ? ? 可以看到打印出來(lái)的結(jié)果是一個(gè)有序的數(shù)組，原因是每次打印堆頂?shù)脑厝缓缶蛣h除該堆頂元素并且進(jìn)行了向下調(diào)整，調(diào)整完之后此時(shí)堆頂元素就是第二小的元素，所有才能打印出有序的序列。?

9、 實(shí)現(xiàn)堆排序

? ? ? ? 以上的測(cè)試可以發(fā)現(xiàn)是在數(shù)組arr中進(jìn)行的，但是原數(shù)組a并沒(méi)有受到改變，若想實(shí)現(xiàn)排序，則必須在原數(shù)組內(nèi)對(duì)原數(shù)組里的順序進(jìn)行排序。

? ? ? ? 堆排序代碼如下：

void test2()//堆排序
{Heap hp;HeapInit(&hp);//初始化int arr[] = { 7,8,3,5,1,9,4,5 };//創(chuàng)建一個(gè)數(shù)組int k = sizeof(arr) / sizeof(int);//對(duì)原數(shù)組進(jìn)行建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, k, i);//}//建完堆之后不一定是有序的數(shù)組，因此還需要對(duì)其進(jìn)行調(diào)整int end = sizeof(arr) / sizeof(int) - 1;while (end > 0){Swap(&arr[0], &arr[end]);//堆頂元素與堆尾元素進(jìn)行交換AdjustDown(arr, end, 0);//向下調(diào)整到堆尾的前一個(gè)元素end--;//堆尾下標(biāo)--，準(zhǔn)備下一次的交換}//打印for (int i = 0; i < k; i++){printf("%d ", arr[i]);}
}int main()
{test1();return 0;}

? ? ? ? 首先在原數(shù)組a中進(jìn)行建堆，建完堆之后不代表數(shù)組a就是有序的，因此還需要對(duì)其進(jìn)行調(diào)整，我們可以保證的是數(shù)組在建完堆之后堆頂?shù)脑厥亲钚〉?#xff0c;因此把堆頂元素跟堆里的最后一個(gè)元素進(jìn)行交換（用end表示堆尾的下標(biāo)），然后從堆頂開(kāi)始向下調(diào)整到end的前一個(gè)位置結(jié)束調(diào)整，思路與堆的刪除相似。

? ? ? ? 從上圖分析來(lái)看，最后會(huì)得到一組降序的數(shù)組，因此得出結(jié)論建立小堆得到的是降序，而建立大堆得到的是升序。

三、TOP-K的實(shí)現(xiàn)

? ? ? ? 一般我們要查詢某個(gè)專業(yè)的前十名，或者前世界500強(qiáng)的公司有哪些的時(shí)候都會(huì)用到TOP-K來(lái)解決，當(dāng)要搜索的范圍很大的時(shí)候，用正常的排序是難以解決的，比如從10億個(gè)數(shù)中求出前五個(gè)最大的數(shù)，這時(shí)候如果把10億個(gè)數(shù)排好序則要耗費(fèi)大量的內(nèi)存，很明顯排序的辦法不行。

? ? ? ? 這時(shí)候就需要堆來(lái)解決了，可以先建立一個(gè)5個(gè)數(shù)字的小堆，然后從這10個(gè)數(shù)中不斷的取出數(shù)據(jù)跟堆頂元素進(jìn)行比較，如果比堆頂元素大則替換堆頂元素然后再進(jìn)行向下調(diào)整堆，最后堆里的5個(gè)元素就10億中最大的5個(gè)元素。用堆解決的優(yōu)勢(shì)在于這10億個(gè)數(shù)不需要全部拿到內(nèi)存中，而是存在磁盤(pán)里的文件中就可以進(jìn)行對(duì)比了，需要文件操作函數(shù)來(lái)實(shí)現(xiàn)。

? ? ? ? 這里我就用1000個(gè)數(shù)作為測(cè)試用例，TOP-K代碼如下：

void CreatData()//創(chuàng)造數(shù)據(jù)
{int n = 1000;//這里我們只創(chuàng)建1000個(gè)數(shù)用來(lái)測(cè)試srand(time(0));//生成隨機(jī)數(shù)FILE* fin = fopen("data.txt", "w");//以寫(xiě)的方式打開(kāi)文件if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; i++){int x = rand() % 10000;//生成10000以內(nèi)的隨機(jī)值fprintf(fin, "%d\n", x);//把這些值寫(xiě)進(jìn)文件中}fclose(fin);//關(guān)閉文件fin = NULL;
}void TOP_K(int k)//選出5個(gè)最大的數(shù)
{FILE* fin = fopen("data.txt", "r");//以讀的方式打開(kāi)文件if (fin == NULL){perror("fopen error");return;}//創(chuàng)建數(shù)組int* arr = (int*)malloc(sizeof(int)*k);if (arr == NULL){perror("malloc error");return;}//倒數(shù)據(jù)for (int i = 0; i < k; i++){fscanf(fin, "%d", arr + i);//把文件里的前五個(gè)數(shù)給到數(shù)組arr，準(zhǔn)備建堆}//建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, k, i);//向下調(diào)整建立小堆}//TOP-Kint val = 0;//創(chuàng)建val變量while (!feof(fin))//遍歷文件內(nèi)容{fscanf(fin, "%d", &val);//把文件里的值以%d的形式給到val變量if (val > arr[0])//如果val的值大于堆頂元素{arr[0] = val;//將val的值賦給堆頂AdjustDown(arr, k, 0);//并且重新向下調(diào)整堆，保證數(shù)組是一個(gè)堆}}//打印數(shù)組for (int i = 0; i < k; i++){printf("%d ", arr[i]);}fclose(fin);//關(guān)閉文件fin = NULL;
}int main()
{CreatData();//創(chuàng)建數(shù)據(jù)TOP_K(5);//TOP-K實(shí)現(xiàn)return 0;}

? ? ? ? 創(chuàng)建文件數(shù)據(jù)的結(jié)果：

????????運(yùn)行結(jié)果：

?????????從結(jié)果可以看到TOP-K確實(shí)幫助我們從1000個(gè)數(shù)中找出了最大的五個(gè)數(shù)。

結(jié)語(yǔ)：

? ? ? ? 以上就是關(guān)于堆的一系列的解析與延申，堆的重點(diǎn)在于對(duì)向上調(diào)整和向下調(diào)整的理解，這兩個(gè)調(diào)整法才是創(chuàng)建堆的核心。希望本文可以帶給你更多的收獲，如果本文對(duì)你起到了幫助，希望可以動(dòng)動(dòng)小指頭幫忙點(diǎn)贊👍+關(guān)注😎+收藏👌！如果有遺漏或者有誤的地方歡迎大家在評(píng)論區(qū)補(bǔ)充~！！謝謝大家！！(?′?`?)