前言：

之前我們學(xué)習(xí)了順序表、鏈表以及棧和隊(duì)列這些數(shù)據(jù)結(jié)構(gòu)，但這些數(shù)據(jù)結(jié)構(gòu)都是線性的（一對(duì)一）。接下來要學(xué)習(xí)非線性的數(shù)據(jù)結(jié)構(gòu)——樹（二叉樹），相比前面的，樹的結(jié)構(gòu)更加復(fù)雜，話不多說，直接進(jìn)入正題吧。

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

1.樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是一對(duì)多（也有可能是一對(duì)一） 的關(guān)系。它是由n（n>=0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋?像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)
除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1<= i
<= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼，因此樹是遞歸定義的。

現(xiàn)實(shí)中的樹和數(shù)據(jù)結(jié)構(gòu)中的樹，例如：

注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

2.樹的相關(guān)概念

樹的相關(guān)概念是指樹的根、分枝和葉子等等之間的聯(lián)系，與人類的親緣關(guān)系類似。

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A是一對(duì)6，所以A的度為6
葉節(jié)點(diǎn)或終端結(jié)節(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)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(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）棵互不相交的樹的集合稱為森林；

注意：在計(jì)算節(jié)點(diǎn)的層次的時(shí)候，從最上面的節(jié)點(diǎn)往下數(shù)可以從0開始，也可以從1開始，但是更推薦從1開始。
因?yàn)闃淇赡苁强諛?、只有一個(gè)節(jié)點(diǎn)的樹或者是有多個(gè)節(jié)點(diǎn)的樹，如果從0開始計(jì)算，那么節(jié)點(diǎn)的層次（或者說樹的高度）當(dāng)為0時(shí)到底是空樹還是只有一個(gè)節(jié)點(diǎn)的樹不易分清，所以為了方便數(shù)樹的高度，從1開始比較好。

3.樹的存儲(chǔ)

樹結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來就比較麻煩了，既要保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法。（又稱左孩子右兄弟表示法）

struct TreeNode
{int val;struct TreeNode* firstchild;struct TreeNode* nextbrother;
};

一個(gè)節(jié)點(diǎn)可以任意指向多個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的firstchild指針指向它的第一個(gè)孩子節(jié)點(diǎn)（沒有則指向空指針），nextbrother指針指向它的兄弟節(jié)點(diǎn)（沒有則指向空指針）。

先找到第一個(gè)孩子，（例如B是A的第一個(gè)孩子）然后此時(shí)的第一個(gè)孩子再找他的兄弟，直到為空指針結(jié)束。

TreeNode* Anode假設(shè)為節(jié)點(diǎn)A
找A的第一個(gè)孩子B節(jié)點(diǎn)：TreeNode* child = Anode->firstchild；
while(child)直到空結(jié)束
{
…………
child = child->nextbrother;
}

4.樹在實(shí)際中的運(yùn)用

我們平時(shí)使用電腦文件系統(tǒng)的目錄就是樹結(jié)構(gòu)，打開此電腦，有D盤、C盤等，每層又有多個(gè)文件。

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

1.概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合。
1.最多兩個(gè)節(jié)點(diǎn)，也可以是1個(gè)或者0個(gè)
2. 由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出，二叉樹不存在度大于2的結(jié)點(diǎn)，并且二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

注意：對(duì)于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

現(xiàn)實(shí)中的二叉樹：

2.特殊的二叉樹

（1）滿二叉樹

概念：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為h，且結(jié)點(diǎn)總數(shù)是2^h - 1 ，則它就是滿二叉樹。

每一層都是滿的：2^(i-1)個(gè)節(jié)點(diǎn)（i是某一層的位置）
F(h) = 2 ^ 0 + 2 ^ 1 + ……+2 ^ (h-2) + 2 ^ (h-1)等比數(shù)列求和

假設(shè)這個(gè)二叉樹的節(jié)點(diǎn)是N個(gè)
N = 2 ^ h - 1 => h = log(N+1) （log以2為底）

（2）完全二叉樹

概念：完全二叉樹是在滿二叉樹的基礎(chǔ)上變化的。假設(shè)它的高度是h，那么它的前h-1層是滿的，最后一層可能是滿的，也可能是不滿的，并且它的最后一層必須從左到右是連續(xù)的。滿二叉樹是特殊的完全二叉樹。

因此，完全二叉樹的節(jié)點(diǎn)總個(gè)數(shù)是有范圍的。當(dāng)它為滿二叉樹時(shí)，也就是節(jié)點(diǎn)總個(gè)數(shù)最多的情況下，它的節(jié)點(diǎn)總個(gè)數(shù)是2^h - 1；當(dāng)最后一層只有一個(gè)節(jié)點(diǎn)，也就是節(jié)點(diǎn)總個(gè)數(shù)最少的情況下，它的節(jié)點(diǎn)總個(gè)數(shù)是2 ^ (h-1)，所以節(jié)點(diǎn)范圍：【2 ^ (h-1) ， 2 ^ h - 1】。

3.二叉樹的性質(zhì)

1.如果根節(jié)點(diǎn)的層數(shù)為1，則一個(gè)非空二叉樹的第h層最多有2^(h-1)個(gè)節(jié)點(diǎn)；
2.如果根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹最多一共有2^h-1個(gè)節(jié)點(diǎn)；
3.對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2，則滿足公式n0=n2+1；
4.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h=log(n+1)

4.二叉樹的存儲(chǔ)

二叉樹的存儲(chǔ)方式分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

(1)順序存儲(chǔ)

順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。

使用數(shù)組存儲(chǔ)時(shí)有一個(gè)規(guī)律：

可在任意位置通過下標(biāo)找到父親或者孩子
注意：前提是滿二叉樹或者完全二叉樹才能用這個(gè)規(guī)律

所以，對(duì)于非完全二叉樹，使用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)更適合。

總結(jié)：滿二叉樹或者完全二叉樹適合用數(shù)組存儲(chǔ)

(2)鏈?zhǔn)酱鎯?chǔ)

二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)是用鏈表來表示一個(gè)二叉樹，分為三個(gè)作用域（數(shù)據(jù)域和左右指針域），左右指針來存儲(chǔ)左右孩子的地址。

三、二叉樹的順序結(jié)構(gòu)及實(shí)現(xiàn)

1.二叉樹的順序結(jié)構(gòu)

普通的二叉樹是不適合用數(shù)組來存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲(chǔ)。現(xiàn)實(shí)中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲(chǔ)，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

2.堆的概念及結(jié)構(gòu)

堆：非線性結(jié)構(gòu)的二叉樹，更準(zhǔn)確的說是完全二叉樹。適合用數(shù)組存儲(chǔ)。

堆分為兩種：根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
小堆：樹中任意一個(gè)父親都<=孩子（比的是節(jié)點(diǎn)的值）
大堆：樹中任意一個(gè)父親都>=孩子

3.堆的實(shí)現(xiàn)

（1）初始化堆

初始化堆有兩種方式。
第一種：把結(jié)構(gòu)體指向的數(shù)組里面置空（沒有元素），有效個(gè)數(shù)和容量置為0

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

第二種：接收外來數(shù)組的大小n，動(dòng)態(tài)開辟大小為n的空間，把數(shù)據(jù)拷貝到結(jié)構(gòu)體指向的數(shù)組里

void HPInitArray(HP* php, HPDataType* a, int n)
{assert(php);assert(a);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");exit(-1);}php->size = n;php->capacity = n;memcpy(php->a, a, sizeof(HPDataType) * n);for (int i = 1; i < n; i++){AdjustUp(php->a, i);}

AdjustUp 是向上調(diào)整算法，下面會(huì)分析。

（2）銷毀堆

堆的銷毀不必多說，與順序表的銷毀相同

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

（3）堆的插入

堆的插入采用順序表的尾插（一個(gè)一個(gè)插入），因?yàn)閿?shù)組的尾插效率高（還有尾刪，后面也會(huì)用到）。插入數(shù)據(jù)要考慮擴(kuò)容，因?yàn)榍懊娉跏蓟臅r(shí)候空間大小為0。這里可以設(shè)置一個(gè)變量newcapacity，用條件操作符，如果容量為0，就給初始容量4，否則就是原來容量的兩倍。擴(kuò)容完插入新的數(shù)據(jù)，元素個(gè)數(shù)++。

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* ptr = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (ptr == NULL){perror("realloc fail");exit(-1);}php->a = ptr;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上調(diào)整
}

難道把外來的數(shù)據(jù)一個(gè)一個(gè)插入就行了嗎？其實(shí)不然，我們插入數(shù)據(jù)后要使結(jié)構(gòu)體指向的數(shù)組變成一個(gè)堆，這里要介紹一個(gè)算法。

向上調(diào)整算法

從最后一個(gè)葉子節(jié)點(diǎn)開始向上調(diào)整。以建小堆為例，插入一個(gè)新的數(shù)據(jù)為最后一個(gè)葉子節(jié)點(diǎn)，小堆的特點(diǎn)是父節(jié)點(diǎn)<=孩子節(jié)點(diǎn)，所以要先找到父節(jié)點(diǎn)。

公式：parent = (child - 1) / 2

我們知道，堆的實(shí)現(xiàn)雖然是二叉樹，但它的存儲(chǔ)方式本質(zhì)是數(shù)組，空間是連續(xù)的，所以可以通過孩子節(jié)點(diǎn)下標(biāo)找到父節(jié)點(diǎn)。這時(shí)孩子節(jié)點(diǎn)可以與父節(jié)點(diǎn)比較，如果父節(jié)點(diǎn)大于孩子節(jié)點(diǎn)，就交換，然后孩子節(jié)點(diǎn)向上到達(dá)父節(jié)點(diǎn)的位置，原來父節(jié)點(diǎn)到達(dá)它的父節(jié)點(diǎn)的位置。注意控制孩子節(jié)點(diǎn)的范圍，孩子節(jié)點(diǎn)不可能是堆頂元素，否則就會(huì)越界，所以child>0。如果父子節(jié)點(diǎn)大小關(guān)系滿足小堆特點(diǎn)，就跳出循環(huán)，此時(shí)該數(shù)組就是小堆了。

向上調(diào)整的前提：該數(shù)組原來是小堆或者大堆

既然如此，那插入一個(gè)數(shù)據(jù)前怎么知道這個(gè)數(shù)組已經(jīng)是小堆或者大堆了呢？其實(shí)這里指針?biāo)赶虻臄?shù)組原來什么也沒有，是一個(gè)一個(gè)插入數(shù)據(jù)的，而我每插入一個(gè)數(shù)據(jù)就調(diào)整一次，相當(dāng)于說我要插入下一個(gè)數(shù)據(jù)時(shí)前面的數(shù)據(jù)已經(jīng)調(diào)整為小堆了，那么插入下一個(gè)數(shù)據(jù)我就調(diào)整這個(gè)數(shù)據(jù)和它的父節(jié)點(diǎn)的關(guān)系就行了。

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

（4）堆的刪除

刪除堆的一個(gè)元素采用順序表的尾刪，但是這里要注意的是僅僅刪除堆的最后一個(gè)元素是沒有意義的。假如是小堆，那么它有個(gè)特點(diǎn)，它的堆頂元素一定是所以元素里最小的，所以應(yīng)該刪除堆頂元素?？墒菙?shù)組的頭刪要挪動(dòng)數(shù)據(jù)，比較麻煩，所以這里把堆頂元素與最后一個(gè)元素交換，然后再尾刪，就可以把最小的元素刪除了。但是刪除之后，堆頂?shù)脑卮笮【筒淮_定了，此時(shí)不一定是小堆。這里要介紹另一個(gè)算法。

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

向下調(diào)整算法

從堆頂元素開始往下調(diào)整，因?yàn)榍懊娴匿亯|只改變了堆頂元素，所以堆頂元素是父節(jié)點(diǎn)，可以通過以下公式找到它的孩子節(jié)點(diǎn)：

左孩子：child = parent * 2 + 1
右孩子：child = parent * 2 + 2

那么問題來了，是選擇左孩子還是選擇右孩子？這里我們可以默認(rèn)選擇左孩子，然后加一個(gè)判斷，如果左孩子的值大于右孩子的值，左孩子下標(biāo)加1，變成右孩子。因?yàn)橄蛳抡{(diào)整變成小堆父節(jié)點(diǎn)所要交換的節(jié)點(diǎn)是兩個(gè)孩子節(jié)點(diǎn)中的較小的。接著比較父節(jié)點(diǎn)與孩子節(jié)點(diǎn)的大小關(guān)系，如果父節(jié)點(diǎn)大于孩子節(jié)點(diǎn)，就交換（父節(jié)點(diǎn)與孩子交換就是與較小的孩子節(jié)點(diǎn)交換），然后父節(jié)點(diǎn)到達(dá)孩子節(jié)點(diǎn)的位置，孩子節(jié)點(diǎn)到到達(dá)它的左孩子節(jié)點(diǎn)的位置。不滿足條件說明此時(shí)是小堆就跳出循環(huán)。

注意：這里要控制一個(gè)細(xì)節(jié)，孩子節(jié)點(diǎn)下標(biāo)的范圍小于元素個(gè)數(shù)。同時(shí)，如果一個(gè)父節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)的情況下（只有左孩子），那么這個(gè)左孩子的下標(biāo)加1就越界了。
child + 1 < n ——這個(gè)條件成立說明只有左孩子沒有右孩子

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[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

（5）獲取堆頂元素/堆的元素個(gè)數(shù)/判空

//獲取堆頂元素
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}
//獲取堆的元素個(gè)數(shù)
int HPSize(HP* php)
{assert(php);return php->size;
}
//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

4.堆排序

我們要把堆里面的數(shù)據(jù)排序（以升序?yàn)槔?#xff09;，有兩種方式，一個(gè)是打印出來有序，另一個(gè)是原地使數(shù)組有序。

（1）堆排序版本1

把數(shù)據(jù)一個(gè)一個(gè)插入堆中，只要數(shù)組不為空就取堆頂元素，然后刪除堆頂元素，直到把所有元素打印出來為升序。

void HeapSort(int* a, int n)
{HP hp;HPInit(&hp);int i = 0;for (i = 0; i < n; i++){HPPush(&hp, a[i]);}HPPrint(&hp);while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);
}

這個(gè)方法有缺點(diǎn)：
1.頻繁的擴(kuò)容造成空間復(fù)雜度的消耗
2.先要有一個(gè)堆的數(shù)據(jù)結(jié)構(gòu)

（2）堆排序版本2——對(duì)數(shù)組原地排序

假如一個(gè)數(shù)組進(jìn)行堆排序后還要使用，此時(shí)只對(duì)它打印出來排序就不適合了。所以要對(duì)數(shù)組原地進(jìn)行堆排序，使數(shù)組的內(nèi)容有序。

例如：
原來的數(shù)組：65,100,70,32,50,60
排序后的數(shù)組：32,50,60,65,70,100

在排序前我們要建堆，那么是建小堆還是建大堆？
先來建小堆：
以升序?yàn)槔?#xff0c;我們?cè)谇懊娴亩雅判蚴谴蛴〕鰜淼?#xff0c;用向上調(diào)整法是建小堆。這里也用建小堆的方法，小堆建成后堆頂?shù)脑厥亲钚〉?#xff0c;所以這個(gè)元素排在數(shù)組的第一個(gè)；然后是次小的，依次從前往后排，直到把數(shù)組里的元素從前往后全部排完就是升序了。

但是先以建小堆的方法有缺陷：
分析：堆頂?shù)脑厥嵌旬?dāng)中最小的依次對(duì)應(yīng)數(shù)組從前往后排，每次排完一個(gè)數(shù)據(jù)，要從后面的數(shù)據(jù)中找出次小的，但問題在于排完的那個(gè)數(shù)據(jù)的后一個(gè)數(shù)據(jù)不一定是次小的，所以后面的數(shù)據(jù)要重新建堆，重新建的堆的堆頂元素就是次小的。而每次重新建堆使時(shí)間復(fù)雜度變大，造成效率很低。

向上調(diào)整法一個(gè)數(shù)據(jù)遍歷時(shí)時(shí)間復(fù)雜度為：logN
有N個(gè)數(shù)據(jù)所以建堆的時(shí)間復(fù)雜度為：N * logN
每排完一個(gè)數(shù)據(jù)都要建堆一次時(shí)間復(fù)雜度為：N * (N * logN)
相當(dāng)于建N次小堆

所以這里應(yīng)該是建大堆，大堆的堆頂是堆中最大的元素，可是它排在數(shù)組的第一個(gè)位置，怎么讓它到數(shù)組的最后一個(gè)位置呢？

在這步可以采用堆的刪除的思路。把堆頂?shù)脑嘏c最后一個(gè)元素交換，這時(shí)最大的元素就到了它應(yīng)該在的位置，然后接下來的步驟很關(guān)鍵，不是真的把最后一個(gè)元素刪除，那最大的元素排在最后不就沒了嗎？所以這里我們可以定義一個(gè)變量end，它指向的是數(shù)組的最后一個(gè)元素，完成交換后向下調(diào)整，調(diào)整的范圍是0（第一個(gè)元素）到end的有效個(gè)數(shù)，注意，這時(shí)end指向的那個(gè)元素不在調(diào)整的范圍內(nèi)。然后end減1，控制end>0循環(huán)，因?yàn)樽詈笾挥幸粋€(gè)元素就不需要調(diào)整了，它是最小的。

//建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}//調(diào)整int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}

（3）優(yōu)化堆排序版本2及時(shí)間復(fù)雜度的比較

相較于向上調(diào)整法建堆，使用向下調(diào)整法建堆的時(shí)間復(fù)雜度更優(yōu)秀。前面我們都是使用向上調(diào)整法建堆，那么用向下調(diào)整法是怎么建堆的呢？

我們知道，用向上調(diào)整法建堆是從最后一個(gè)節(jié)點(diǎn)開始，找它的父節(jié)點(diǎn)然后進(jìn)行比較完成建堆。

調(diào)整的執(zhí)行總次數(shù)：每層數(shù)據(jù)個(gè)數(shù) * 向上或向下移動(dòng)的層數(shù)

向上調(diào)整法時(shí)間復(fù)雜度的計(jì)算
如圖：

向下調(diào)整法建堆：
前面使用向下調(diào)整法是從堆頂開始向下調(diào)整，依次比較。這里不是從堆頂開始，而是從下面開始調(diào)整。找到最后一個(gè)父節(jié)點(diǎn)，（只要是父節(jié)點(diǎn)一定有孩子節(jié)點(diǎn)），然后進(jìn)行比較、調(diào)整；接著再到前一個(gè)父節(jié)點(diǎn)進(jìn)行前面的操作，最終建成堆。

找最后一個(gè)父節(jié)點(diǎn)：
最后一個(gè)孩子節(jié)點(diǎn)：child = n-1
有孩子找父親：（child-1）/ 2
所以最后一個(gè)父節(jié)點(diǎn)：(n - 1 - 1) / 2

向下調(diào)整法時(shí)間復(fù)雜度的計(jì)算
如圖：

通過對(duì)比：向上調(diào)整與向下調(diào)整的總次數(shù)相比多了2 ^ (h-1)，也就是說多了一層（最后一層）的計(jì)算。最后一層占比大約整體的一半，所以向下調(diào)整法建堆更好。

void HeapSort(int* a, int n)
{//建堆//選擇向上調(diào)整——O(N*log(N))/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*///選擇向下調(diào)整——O(N)int i = 0;for ( i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//調(diào)整int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

（4）TopK問題

假設(shè)有N個(gè)數(shù)據(jù)，找出最大的前K個(gè)

1.讀取文件的前K個(gè)數(shù)據(jù)，在內(nèi)存數(shù)組中建一個(gè)小堆
2.再依次讀取后面的數(shù)據(jù)，跟堆頂元素比較，只要比堆頂元素大就替換堆頂元素進(jìn)堆，然后向下調(diào)整
3.讀完所有數(shù)據(jù)，堆里面的數(shù)據(jù)就是最大的前K個(gè)

這個(gè)方法很巧妙，建小堆這樣堆頂?shù)脑厥嵌阎凶钚〉?#xff0c;只要比它大就交換進(jìn)堆。大的數(shù)據(jù)進(jìn)堆往下沉在堆底，只有堆里面是最大的前K個(gè)才沒有交換。當(dāng)堆里面是最大的前K個(gè)時(shí)，因?yàn)槭切《?#xff0c;堆頂是堆中元素最小的，但是它又比不在堆里面的元素都要大。就算剛開始堆里面已經(jīng)有K-1個(gè)元素在所有元素最大的前K個(gè)元素的范圍內(nèi)，進(jìn)行向下調(diào)整保持小堆那么必然有一個(gè)元素在堆頂且這個(gè)元素小于后面的某個(gè)數(shù)據(jù)，讀取到后面的那個(gè)元素就交換然后向下調(diào)整，最大的前K個(gè)就找到了。
如果是建大堆，大堆的堆頂元素是堆中最大的，比它大才能進(jìn)堆，萬一剛開始的堆建好后正好堆頂?shù)脑厥撬性刂凶畲蟮?#xff0c;那豈不是把所有元素都擋住了。

void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("minheap fail");return;}int i = 0;for (i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}for (i = (k - 2) / 2; i >= 0; i--){AdjustDown(minheap, k, i);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (minheap[0] < x){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (i = 0; i < k; i++){printf("%d ", minheap[i]);}free(minheap);fclose(fout);
}
void CreateNDate()
{// 造數(shù)據(jù)int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
int main()
{CreateNDate();PrintTopK("data.txt", 5);return 0;
}

感謝觀看~