文章目錄

前言

一、樹

(一)、概念

1、樹的定義

(二)、樹的定義

1、樹為什么是遞歸定義的？

2、如何定義樹(如何表達(dá)一棵樹)

解決方案一：假設(shè)我們得知該樹的度

解決方案二：順序表

解決方案三：左孩子右兄弟表示法

二、二叉樹

(一)、概念

(二)、特殊二叉樹

1、斜樹

2、滿二叉樹

3、完全二叉樹

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

(四)、二叉樹的性質(zhì)

(五)、二叉樹的存儲(chǔ)結(jié)構(gòu)

1、順序存儲(chǔ)結(jié)構(gòu)：

2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

三、堆

(一)、堆的概念

1、堆的定義：

2、堆的性質(zhì)：

3、堆的特點(diǎn)：

(二)、堆類型的聲明

(三)、堆的實(shí)現(xiàn)

1、Heap.h 的實(shí)現(xiàn)

2、Heap.c 的實(shí)現(xiàn)

1、初始化

2、銷毀

3、交換

4、向上調(diào)整

5、push

6、向下調(diào)整

7、pop

8、獲取堆頂數(shù)據(jù)

9、判空

(四)、堆排序

1、建堆算法

方法一：利用向上調(diào)整建堆

方法二：利用向下調(diào)整建堆

2、堆排序

(五)、TOP-K 問題

解決方案一：

解決方案二：

總結(jié)

前言

路漫漫其修遠(yuǎn)兮，吾將上下而求索；

一、樹

(一)、概念

1、樹的定義

在之前學(xué)習(xí)的順序表、鏈表、棧、隊(duì)列均是一對(duì)一的線性結(jié)構(gòu)(此線性為邏輯上的”線性“)，而非線性結(jié)構(gòu)的特點(diǎn)是復(fù)雜；生活中當(dāng)然不僅僅只是一對(duì)一的問題，面對(duì)一對(duì)多的問題，我們又該如何解決呢？利用一對(duì)多的數(shù)據(jù)結(jié)構(gòu)，此處所要講述的”樹“便是一對(duì)多的數(shù)據(jù)結(jié)構(gòu)；

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n (n>=0) 個(gè)有限結(jié)點(diǎn)組成的具有層次關(guān)系的集合，將此結(jié)構(gòu)叫做樹的原因是因?yàn)榇私Y(jié)構(gòu)像一棵倒掛的樹，即其根在上，而葉朝下；

當(dāng)n = 0 時(shí)，稱此樹為空樹

在任意一棵非空樹中(如下圖所示)：

• 1、有且只有一個(gè)特定的節(jié)點(diǎn)稱為根(Root)結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)；
• 2、當(dāng)n>1 時(shí)，其余節(jié)點(diǎn)可以分為m(m>0)個(gè)不相交的有限集T1、T2...Tm,其中一個(gè)集合本身又是一棵樹，并且稱為根節(jié)點(diǎn)的子樹(SubTree),每棵樹的根節(jié)點(diǎn)可以有0個(gè)或者多個(gè)后繼；
• 3、樹是遞歸定義的；

樹為什么是遞歸定義的？

• 請(qǐng)繼續(xù)往下看，下文中會(huì)有解釋；?

樹的定義中運(yùn)用到了樹的概念；下圖中的子樹T1與子樹T2 為上圖根節(jié)點(diǎn)A的子樹；當(dāng)然，D、H組成的左子樹與E組成的右子樹又為根節(jié)點(diǎn)B的子樹；F 組成的右子樹與G、I組成的右子樹又作為根節(jié)點(diǎn)C的子樹；

注：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不叫作樹形結(jié)構(gòu)(子樹之間有交集叫做”圖“)；如下圖所示：

樹形結(jié)構(gòu)的特點(diǎn)：

• 1、子樹不相交
• 2、除了根節(jié)點(diǎn)之外(根節(jié)點(diǎn)沒有父節(jié)點(diǎn))。每個(gè)結(jié)點(diǎn)有且有且只有一個(gè)父節(jié)點(diǎn)
• 3、一棵N個(gè)節(jié)點(diǎn)的樹有N-1條邊

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

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(孩子)個(gè)數(shù)稱為該節(jié)點(diǎn)的度；如上圖：節(jié)點(diǎn)A有三個(gè)子樹，故而A的度為3；
• 葉節(jié)點(diǎn)(終端節(jié)點(diǎn))：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)(沒有子節(jié)點(diǎn)的節(jié)點(diǎn))；如上圖中，節(jié)點(diǎn)J、F、M、L、H、I為葉節(jié)點(diǎn)
• 分支節(jié)點(diǎn)(非終端節(jié)點(diǎn))：度不為0的節(jié)點(diǎn)；如上圖：B、C、D、E、G、K 為非終端節(jié)點(diǎn)；
• 父節(jié)點(diǎn)(雙親節(jié)點(diǎn))：若一個(gè)節(jié)點(diǎn)中包含子節(jié)點(diǎn)，那么此節(jié)點(diǎn)便會(huì)被稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；如上圖：節(jié)點(diǎn)A為節(jié)點(diǎn)B的父節(jié)點(diǎn)；
• 子節(jié)點(diǎn)(孩子節(jié)點(diǎn))：一個(gè)節(jié)點(diǎn)含有子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；如上圖：節(jié)點(diǎn)B是節(jié)點(diǎn)A的子節(jié)點(diǎn)；
• 兄弟節(jié)點(diǎn): 具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)；如上圖，節(jié)點(diǎn)B、C、D稱為兄弟節(jié)點(diǎn)
• 樹的度：一棵樹中，節(jié)點(diǎn)中最大的度為該樹的度；如上圖：因?yàn)樵谒泄?jié)點(diǎn)中最大的度為節(jié)點(diǎn)A的3 ，故而該樹的度為3；
• 節(jié)點(diǎn)的層次：從根開始定義，根為第一層，根的子節(jié)點(diǎn)為第二層……以此類推下去；(有些地方從第0層開始計(jì)算樹的層數(shù))
• 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；如上圖：樹的高度為5；
• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：節(jié)點(diǎn)E、J、H 互為堂兄弟節(jié)點(diǎn)；
• 節(jié)點(diǎn)的祖先: 從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)歷分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先，節(jié)點(diǎn)J的祖先有：A、B、E；
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖，所有節(jié)點(diǎn)均為A的子孫、節(jié)點(diǎn)B的子孫有E、F、J；
• 森林：由m(m>0) 棵不相交的樹的集合合稱為森林；(即多棵樹便稱為森林)；

注：

• 在樹的這部分利用樹的相關(guān)概念(樹、葉、分支) 以及人類親緣關(guān)系進(jìn)行命名；
• 一棵樹是由葉節(jié)點(diǎn)(終端節(jié)點(diǎn)) 與 分支節(jié)點(diǎn)(非終端節(jié)點(diǎn)) 構(gòu)成的；

節(jié)點(diǎn)層次的概念如何區(qū)分？?

• 看你如何分著走，可以從第0層開始，也可以從第一層開始；一般情況下從第1層開始，因?yàn)闃溥€有空樹的概念，這樣的話，空樹便為第0層；而若從第0層開始，那么空樹只能當(dāng)作 -1層，有點(diǎn)奇怪，但是這樣的表達(dá)沒有問題；

可能你會(huì)聯(lián)想到數(shù)組的下標(biāo)為什么是從0開始的，而不是從1開始？

• 數(shù)組的下標(biāo)從0開始是被逼無奈的；眾所周知，數(shù)組名表示首元素地址，倘若此處有一個(gè)數(shù)組a ，那么a[i] = *(a+i) ; 基于這個(gè)特點(diǎn)，只有數(shù)組的下標(biāo)從0開始，才能滿足此表達(dá)式；--> a[0] = *a ;

樹的高度或深度--> 最大層次的概念

樹的高度或者深度與其從第一層開始還是從第0層開始有關(guān)；如若一棵樹有6層，并且其層次從第一層開始的，那么該樹的高度(深度)便為6；而如若該樹從第0層開始，那么該樹的高度便為5；

此處并沒有特別嚴(yán)格的概念來定義的高度(深度)，由于一般情況下我們樹的層次是從第一層開始的，所以可以將樹的高度當(dāng)作其層數(shù)；但是不要忘記樹的高度的核心 —— 最大層次；

(二)、樹的定義

1、樹為什么是遞歸定義的？

任何一棵樹均是由兩部分組成的：根節(jié)點(diǎn) 與 子樹(即任何一棵樹均包含根和N棵子樹，其中N大于等于0);

樹是由根節(jié)點(diǎn)與子樹構(gòu)成，而子樹又是由根節(jié)點(diǎn)與子樹構(gòu)成，子樹又是由根節(jié)點(diǎn)與子樹構(gòu)成……故而說樹是由遞歸構(gòu)成的；

如何理解遞歸?

• 遞歸的 ”核心“ 思想：大事化小
• 遞歸：大問題可以拆分為小問題，小問題可以拆解稱更小的問題……直到這個(gè)問題被拆成不可以再拆解的問題才會(huì)停止；而這些問題是相似的；

回顧之前在C語(yǔ)言階段學(xué)習(xí)的遞歸，遞歸有兩個(gè)條件

遞歸又稱為”分治“，即分而治之(將大問題化為小問題)；

用圖像來理解：

由上圖可知，A這棵樹，由根節(jié)點(diǎn)A、子樹B、子樹C、子樹D構(gòu)成；而子樹B又由根節(jié)點(diǎn)B、子樹E與子樹F構(gòu)成，子樹E由根節(jié)點(diǎn)E、子樹J構(gòu)成，子樹F由根節(jié)點(diǎn)F構(gòu)成…… 從上圖中可以清楚地看見，一棵樹由一個(gè)根節(jié)點(diǎn)與N個(gè)子樹構(gòu)成(N>=0) ， 而一個(gè)子樹又由一個(gè)根節(jié)點(diǎn)與N個(gè)子樹構(gòu)成(N>=0)……當(dāng)這棵樹只有一個(gè)根節(jié)點(diǎn)的時(shí)候便不再分下去。

2、如何定義樹(如何表達(dá)一棵樹)

在前面的學(xué)習(xí)，在定義單鏈表的結(jié)點(diǎn)時(shí)，由于單鏈表的結(jié)點(diǎn)需要一個(gè)數(shù)值域來存放數(shù)據(jù)，一個(gè)指針域來存放下一個(gè)結(jié)點(diǎn)的地址，所以在定義單鏈表結(jié)點(diǎn)類型的時(shí)候，定義一個(gè)數(shù)值域與指針域；在雙鏈表中，需要一個(gè)數(shù)值域來存放數(shù)據(jù)，兩個(gè)指針域分別指向前一個(gè)結(jié)點(diǎn)與后一個(gè)結(jié)點(diǎn)；故而在定義雙鏈表結(jié)點(diǎn)類型的時(shí)候會(huì)定義一個(gè)數(shù)值域與兩個(gè)指針域；

而樹，是由根節(jié)點(diǎn)與子樹(孩子)構(gòu)成；一棵樹只有一個(gè)根節(jié)點(diǎn)，這是顯而易見的；但由于并不知道有多少子節(jié)點(diǎn)，定義樹的時(shí)候究竟要定義多少個(gè)孩子就是一個(gè)問題；

解決方案一：假設(shè)我們得知該樹的度

利用樹的度建立一個(gè)指針數(shù)組，在將此指針數(shù)組與數(shù)據(jù)封裝在一個(gè)結(jié)構(gòu)體中，如下圖所示：??

注：如果此處的N很大，那么此結(jié)構(gòu)是存在空間浪費(fèi)的；

解決方案二：順序表

(在未知數(shù)的度的情況下)使用順序表來存放子節(jié)點(diǎn)的地址

方案一相當(dāng)于使用的是靜態(tài)的數(shù)組來存放子節(jié)點(diǎn)的地址，而方案二相當(dāng)于是動(dòng)態(tài)的數(shù)組來存放子節(jié)點(diǎn)的地址；

此處使用順序表本質(zhì)上也是在使用數(shù)組，只不過相較于方案一，此處的數(shù)組中存放子節(jié)點(diǎn)地址的空間是動(dòng)態(tài)開辟的；這種方法不會(huì)浪費(fèi)空間并且很直觀，但是不好控制、訪問；

解決方案三：左孩子右兄弟表示法

就定義兩個(gè)指針(leftChild、rightBrother)，不在乎有多少個(gè)孩子，定義如下：

?左孩子右兄弟表示法究竟特點(diǎn)在何處？

• 讓孩子去鏈接孩子，兄弟去鏈接兄弟

如下圖所示：

如上圖所示，無論一個(gè)結(jié)點(diǎn)會(huì)有多少個(gè)孩子，leftChild 均會(huì)指向其最左邊的孩子，剩余的孩子右rightBrother (親兄弟)解決；

二、二叉樹

(一)、概念

二叉樹(Binary Tree) 是n (n>=0) 個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(即空二叉樹)，或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹構(gòu)成，如下圖：

注：

1、二叉樹中節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)小于等于2，二叉樹的度最大為2；

2、二叉樹中的子樹存在左右之分，次序不能顛倒，故而二叉樹又稱為有序樹；

3、即使樹中的節(jié)點(diǎn)只有一棵樹，也是需要區(qū)分此數(shù)為左子樹還是右子樹；

二叉樹的均為以下的二叉樹復(fù)合而成：

即，二叉樹的五種基本形態(tài)：

1、空二叉樹

2、只有一個(gè)根節(jié)點(diǎn)

3、根節(jié)點(diǎn)只有左子樹

4、根節(jié)點(diǎn)只有右子樹

5、根節(jié)點(diǎn)既有左子樹又有右子樹

(二)、特殊二叉樹

1、斜樹

顧名思義，斜樹就是斜著的樹(二叉樹只有左右之分，故而可向左斜也可向右斜)

• 左斜樹：所有節(jié)點(diǎn)都只有左子樹的二叉樹
• 右斜樹：所有節(jié)點(diǎn)均只有右子樹的二叉樹

斜樹的特點(diǎn)：每一層均只有一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的個(gè)數(shù)與其樹的高度(深度)相同(從第一層開始算)，如下圖：

2、滿二叉樹

在一棵二叉樹中，如果所有分支節(jié)點(diǎn)均存在左子樹與右子樹，并且所有的葉節(jié)點(diǎn)均在同一層，這樣的二叉樹便稱為滿二叉樹；換句話說，此樹的每一層均達(dá)到最大值，倘若此樹的層次為 k ,那么該樹的總節(jié)點(diǎn)個(gè)數(shù)為： 2^k-1 。如下圖：

滿二叉樹的特點(diǎn)：

1、葉節(jié)點(diǎn)只能出現(xiàn)在最下面的一層；

2、非葉節(jié)點(diǎn)的度一定為2；

3、在同樣高度(深度) 的二叉樹中，滿二叉樹的節(jié)點(diǎn)個(gè)數(shù)最多，葉節(jié)點(diǎn)最多；

3、完全二叉樹

對(duì)一棵有n個(gè)節(jié)點(diǎn)的二叉樹按層序進(jìn)行編號(hào)，如果編號(hào)為i (1 <= i <= n)的節(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為 i 的節(jié)點(diǎn)在二叉樹中的位置完全相同，那么此二叉樹便稱為完全二叉樹；

換句話說，完全二叉樹如果有k 層，其(k-1) 層均是滿的，最后一層即第k層不是滿的，但節(jié)點(diǎn)從左向右是連續(xù)的(中間沒有空節(jié)點(diǎn))；

注：滿二叉樹是一種特殊的完全二叉樹；

?

注：完全二叉樹的所有節(jié)點(diǎn)與其同深度的滿二叉樹，他們按層序編號(hào)相同的節(jié)點(diǎn)，是一一對(duì)應(yīng)的關(guān)系；

按層序編號(hào)，例如，上圖中的左邊的圖中，其每一層的編號(hào)均是連續(xù)的，故而左圖中的樹為完全二叉樹；而右圖中最后一層的編號(hào)并不是連續(xù)的，編號(hào)10與11 空擋了，故而該樹并不是完全二叉樹；

完全二叉樹的特點(diǎn)：(在頭腦中過一遍完全二叉樹的圖形即可，無需記憶)

1、葉節(jié)點(diǎn)只能出現(xiàn)在最下面的兩層

2、最后一層的葉節(jié)點(diǎn)一定會(huì)集中在左邊連續(xù)位置上

3、倒數(shù)第二層，如果有葉節(jié)點(diǎn)，一定在右部連續(xù)的位置上

4、如果一個(gè)節(jié)點(diǎn)的度為1，那么該節(jié)點(diǎn)只有左孩子，即不會(huì)存在有右孩子的情況

5、同樣節(jié)點(diǎn)數(shù)的二叉樹中，完全二叉樹的深度最小

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

(四)、二叉樹的性質(zhì)

性質(zhì)一：在二叉樹的第 h 層，最多有 2^(h-1) 個(gè)節(jié)點(diǎn)，h>=1 即從第一層開始數(shù)；

性質(zhì)二：深度為 h 的二叉樹至多有 2^h -1 個(gè)節(jié)點(diǎn) ,h>=1?即從第一層開始數(shù);

注：最多就是參考的滿二叉樹；

(五)、二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹的實(shí)現(xiàn)可以選擇兩種結(jié)構(gòu)：?1、數(shù)組? ?2、鏈表

即順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；

1、順序存儲(chǔ)結(jié)構(gòu)：

二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是使用一維數(shù)組存儲(chǔ)二叉樹中的節(jié)點(diǎn)，并且數(shù)組的下標(biāo)(節(jié)點(diǎn)的存儲(chǔ)位置)要能夠體現(xiàn)節(jié)點(diǎn)之間的存儲(chǔ)邏輯；

一般數(shù)組只適合用來存儲(chǔ)完全二叉樹，因?yàn)橥耆鏄渲械墓?jié)點(diǎn)均是連續(xù)存放的，不會(huì)浪費(fèi)空間；在現(xiàn)實(shí)中只用使用堆才會(huì)用數(shù)組來存儲(chǔ)節(jié)點(diǎn)，因?yàn)槎训倪壿嫿Y(jié)構(gòu)為完全二叉樹；二叉樹的順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一棵二叉樹；

注：

1、滿二叉樹是一種特殊的完全二叉樹

2、邏輯結(jié)構(gòu)是想象出來的；物理結(jié)構(gòu)是真實(shí)存在的存儲(chǔ)結(jié)構(gòu)；

為什么完全二叉樹適合用數(shù)組來存放？

1、存儲(chǔ)簡(jiǎn)單，不會(huì)浪費(fèi)空間(完全二叉樹的節(jié)點(diǎn)均是連續(xù)的)

2、可以利用下標(biāo)來計(jì)算父子節(jié)點(diǎn)

從上圖中分析我們可以得知，假設(shè)父節(jié)點(diǎn)的下標(biāo)為 i ，如果此父節(jié)點(diǎn)有兩個(gè)孩子，那么其左孩子的下標(biāo)為 2*i+1 ,右孩子的下標(biāo)為 2*i+2 ;

同理，反過來，假設(shè)孩子的下標(biāo)為 j ,如果此孩子為左孩子，那么其父節(jié)點(diǎn)的下標(biāo)為：(j-1)/2 ; 而若此孩子為右孩子，那么其父節(jié)點(diǎn)的下標(biāo)為 : (j-2)/2 ;?

計(jì)算機(jī)中的 "/" 會(huì)去除除法中的余數(shù)而只保留整數(shù)；

假設(shè)父節(jié)點(diǎn)的下標(biāo)為i ,那么左孩子的下標(biāo)為 2*i+1 , 其中1小于2，那么當(dāng)2*i-1 除以2 的時(shí)候結(jié)果就是 i ,當(dāng)然，將這個(gè)1減去計(jì)算結(jié)果也為i，因?yàn)?小于2，不會(huì)對(duì)除2產(chǎn)生影響；同理，右孩子下標(biāo)為 2*i+2 ,即 (1+i)*2 , 右孩子的的下標(biāo)為2的倍數(shù)，只要將2破壞成1或者0，右孩子/2 的結(jié)果便就是父節(jié)點(diǎn)的下標(biāo) i， 故而假設(shè)右孩子的節(jié)點(diǎn)為j ，那么其父節(jié)點(diǎn)的下標(biāo)為 (j-1)/2 (當(dāng)然，也可以用(j-2)/2 來計(jì)算)；

綜上:

• 1、假設(shè)父節(jié)點(diǎn)的下標(biāo)為 i ,（此父節(jié)點(diǎn)有兩個(gè)孩子的情況下）其左孩子的下標(biāo)為: 2*i+1 ,?右孩子的下標(biāo)為：2*i+2?;
• 2、假設(shè)孩子的節(jié)點(diǎn)為 j (無論是左孩子還是右孩子)，其父節(jié)點(diǎn)的下標(biāo)為 ：(j-1)/2?;

2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即用鏈表的形式來存儲(chǔ)二叉樹的節(jié)點(diǎn)，用指針來指示節(jié)點(diǎn)之間的邏輯關(guān)系；在鏈表的結(jié)點(diǎn)中通常是由三個(gè)域組成：數(shù)值域和左右指針域，左指針域用來指向左節(jié)點(diǎn)，右指針域用來指向右節(jié)點(diǎn)；

而鏈?zhǔn)浇Y(jié)構(gòu)又可以分為二叉鏈與三叉鏈；(此處使用的是二叉鏈，后面會(huì)學(xué)習(xí)紅黑樹的時(shí)候會(huì)使用到三叉鏈)；

注：

1、三叉鏈就是在二叉鏈記錄左右孩子結(jié)點(diǎn)的基礎(chǔ)上再多增加一個(gè)指針域來記錄其父節(jié)點(diǎn)的地址；

2、非完全二叉樹中的節(jié)點(diǎn)就適合使用鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)；

三、堆

(一)、堆的概念

1、堆的定義：

堆的物理結(jié)構(gòu)本質(zhì)上是順序存儲(chǔ)的，是線性的。但在邏輯上不是線性的，是的這種邏輯儲(chǔ)存結(jié)構(gòu)。 堆的這個(gè)數(shù)據(jù)結(jié)構(gòu)，里面的成員包括一維數(shù)組，數(shù)組的容量，數(shù)組元素的個(gè)數(shù)，有兩個(gè)直接后繼。

將根節(jié)點(diǎn)最大的堆叫做大根堆(大堆)：大堆中的任何一個(gè)父節(jié)點(diǎn)總是大于等于其子節(jié)點(diǎn)，根節(jié)點(diǎn)為此樹中最大的節(jié)點(diǎn)；

根結(jié)點(diǎn)最小的堆叫做小根堆(小堆)：小堆中任何一個(gè)父節(jié)點(diǎn)總是小于等于其子節(jié)點(diǎn)，根節(jié)點(diǎn)為此樹中最小的節(jié)點(diǎn)；

注：左右孩子之間并無大小關(guān)系，故而大堆與小堆存儲(chǔ)在數(shù)組中的數(shù)據(jù)不一定有序；

常見的堆有二叉堆、斐波那契堆等。

2、堆的性質(zhì)：

• 1、堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)中的值；(堆分為大根堆、小根堆)
• 2、堆總是一棵完全二叉樹；

注：滿二叉樹是一種特殊的完全二叉樹

數(shù)據(jù)結(jié)構(gòu)中堆和棧的概念是完全不同于C語(yǔ)言中堆和棧的概念；

• 數(shù)據(jù)結(jié)構(gòu)中堆指的是用數(shù)組存儲(chǔ)的完全二叉樹，而棧是可以用數(shù)組實(shí)現(xiàn)具有后進(jìn)先出特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)；另外，數(shù)據(jù)結(jié)構(gòu)中給的堆還可以用來做堆排序、解決TOP-K問題；
• 而C語(yǔ)言中的堆和棧是操作系統(tǒng)中存有的概念，堆和棧屬于內(nèi)存區(qū)域的劃分；(利用庫(kù)函數(shù)malloc、calloc、realloc 動(dòng)態(tài)開辟的空間來自于堆；函數(shù)調(diào)用會(huì)創(chuàng)建函數(shù)棧幀，局部變量便是存放在棧中給的)；

3、堆的特點(diǎn)：

• 小根堆(小堆)中的根節(jié)點(diǎn)是整個(gè)二叉樹中最小的節(jié)點(diǎn)；
• 大根堆(大堆)中的根節(jié)點(diǎn)是整個(gè)二叉樹中最大的節(jié)點(diǎn)；

注：可以利用堆的這個(gè)特點(diǎn)找極值做排序，并且效率高；

注：如果給了一個(gè)算法，讓我們判斷它是否為堆，首先是要將數(shù)組中的數(shù)據(jù)還原為堆(建堆算法)，然后再進(jìn)行判斷；

(二)、堆類型的聲明

堆的本質(zhì)是一個(gè)完全二叉樹(底層是數(shù)組實(shí)現(xiàn)的，動(dòng)態(tài)開辟的數(shù)組需要變量size 與變量capacity)，并在此基礎(chǔ)上增加了一些要求：父子節(jié)點(diǎn)之間的大小關(guān)系；

注：

• 1、大堆的父子節(jié)點(diǎn)大小關(guān)系：父節(jié)點(diǎn) >= 子節(jié)點(diǎn)
• 2、小堆的父子節(jié)點(diǎn)大小關(guān)系： 父節(jié)點(diǎn) <= 子節(jié)點(diǎn)
• 3、并沒有約定兄弟之間的大小關(guān)系

類型聲明如下：

?

注：

• 1、堆底層利用數(shù)組來存放數(shù)據(jù)
• 2、利用數(shù)組下標(biāo)可以找到父子節(jié)點(diǎn)(因?yàn)槎岩欢ㄊ且粋€(gè)完全二叉樹)；如果父節(jié)點(diǎn)的下標(biāo)為i，那么其左孩子的節(jié)點(diǎn)下標(biāo)為2*i+1 ,其右孩子的節(jié)點(diǎn)下標(biāo)為 2*2+2；如果孩子的的下標(biāo)為j ，那么父節(jié)點(diǎn)的下標(biāo)為 (j-1)/2;

(三)、堆的實(shí)現(xiàn)

1、Heap.h 的實(shí)現(xiàn)

#pragma once#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>//堆的類型的定義
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HPInit(HP* php);//銷毀
void HPDestroy(HP* php);//交換
void Swap(HPDataType* p1, HPDataType* p2);//向上調(diào)整
void AdjustUp(HPDataType* a, int child);//push
void HPPush(HP* php, HPDataType x);//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent);//pop
void HPPop(HP* php);//獲取堆頂?shù)臄?shù)據(jù)
HPDataType HPTop(HP* php);//判空
bool HPEmpty(HP* php);

注：

為什么會(huì)有向上調(diào)整？

• 堆的規(guī)則：大堆，其父節(jié)點(diǎn)>=子節(jié)點(diǎn) ； 小堆，父節(jié)點(diǎn) <= 子節(jié)點(diǎn) ；當(dāng)你將數(shù)據(jù)放在數(shù)組的結(jié)尾的時(shí)候(size 指向的空間)，要將該數(shù)據(jù)與其父節(jié)點(diǎn)進(jìn)行比較，當(dāng)不符合該堆的特點(diǎn)的時(shí)候就進(jìn)行交換，以滿足堆的結(jié)構(gòu)規(guī)則；將數(shù)據(jù)一個(gè)一個(gè)地向上調(diào)整，便可以維護(hù)該堆地結(jié)構(gòu)；

2、Heap.c 的實(shí)現(xiàn)

1、初始化

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

2、銷毀

//銷毀
void HPDestroy(HP* php)
{//釋放所有動(dòng)態(tài)開辟的空間assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

3、交換

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

4、向上調(diào)整

大堆：

//向上調(diào)整 - 大堆 父節(jié)點(diǎn)>= 子節(jié)點(diǎn)
void AdjustUp(HPDataType* a, int child)
{//利用孩子的下標(biāo)可以找到父節(jié)點(diǎn)的下標(biāo)int parent = (child - 1) / 2;//讓子節(jié)點(diǎn)與父節(jié)點(diǎn)進(jìn)行比較，不符合大堆要求的就交換位置//當(dāng)與根節(jié)點(diǎn)比較交換了之后便停止循環(huán)(最差的情況 - 比較交換到根節(jié)點(diǎn))while (child>0){if (a[parent] < a[child])//不符合大堆 父節(jié)點(diǎn)>=子節(jié)點(diǎn)便交換{Swap(&a[parent], &a[child]);//調(diào)整child = parent;parent = (child - 1) / 2;}else{break;}}}

小堆：

//向上調(diào)整 - 小堆 父節(jié)點(diǎn)<= 子節(jié)點(diǎn)
void AdjustUp(HPDataType* a, int child)
{//利用孩子的下標(biāo)可以找到父節(jié)點(diǎn)的下標(biāo)int parent = (child - 1) / 2;//讓子節(jié)點(diǎn)與父節(jié)點(diǎn)進(jìn)行比較，不符合小堆要求的就交換位置//當(dāng)與根節(jié)點(diǎn)比較交換了之后便停止循環(huán)(最差的情況 - 比較交換到根節(jié)點(diǎn))while (child>0){if (a[parent] > a[child])//不符合小堆 父節(jié)點(diǎn)<=子節(jié)點(diǎn)便交換{Swap(&a[parent], &a[child]);//調(diào)整child = parent;parent = (child - 1) / 2;}else{break;}}}

5、push

//push
void HPPush(HP* php, HPDataType x)
{assert(php);//避空//空間--初次使用空間還是擴(kuò)容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity*sizeof(HPDataType));if (tmp == NULL){perror("HPPush realloc");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;//向上調(diào)整AdjustUp(php->a, php->size -1);}

6、向下調(diào)整

邏輯分析：

• 利用父節(jié)點(diǎn)的下標(biāo)計(jì)算子節(jié)點(diǎn)的下標(biāo)；
• 該父節(jié)點(diǎn)可能沒有子節(jié)點(diǎn)，可能只有一個(gè)子節(jié)點(diǎn)(即左子節(jié)點(diǎn))，或者有兩個(gè)子節(jié)點(diǎn)，分情況討論；
• 假設(shè)法-先假設(shè)左孩子為兩孩子中較大的節(jié)點(diǎn)，如若只有一個(gè)孩子，那么需要比較的也為左孩子；
• 讓父節(jié)點(diǎn)與其子節(jié)點(diǎn)中較大或者較小(取決于堆) 來進(jìn)行比較 --> 與其所有的子孫節(jié)點(diǎn)進(jìn)行比較；
• 向下調(diào)整到右節(jié)點(diǎn)便停止，即沒有孩子的節(jié)點(diǎn) —— 循環(huán)限制的條件；

大堆：

//向下調(diào)整 - 大堆- 讓父節(jié)點(diǎn)與較大的那個(gè)子節(jié)點(diǎn)進(jìn)行比較
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n)//左孩子的下標(biāo)要在數(shù)組合法的范圍內(nèi){//假設(shè)法if (child + 1 < n && a[child + 1] > a[child])//保證有兩個(gè)孩子的情況下{child++;}//與子祖孫節(jié)點(diǎn)進(jìn)行比較if (a[parent] < a[child]){Swap(&a[parent], &a[child]);//調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}

小堆：

//向下調(diào)整 - 小堆- 讓父節(jié)點(diǎn)與較小的那個(gè)子節(jié)點(diǎn)進(jìn)行比較
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n)//左孩子的下標(biāo)要在數(shù)組合法的范圍內(nèi){//假設(shè)法if (child + 1 < n && a[child + 1] < a[child])//保證有兩個(gè)孩子的情況下{child++;}//與子祖孫節(jié)點(diǎn)進(jìn)行比較if (a[parent] > a[child])//小堆 父節(jié)點(diǎn) <= 子節(jié)點(diǎn){Swap(&a[parent], &a[child]);//調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}

注：大堆與小堆的向下調(diào)整的算法區(qū)別在于：

• 1、假設(shè)法中，取左右孩子中較大者還是較小者(取決于該堆是大堆還是小堆)
• 2、父節(jié)點(diǎn)與其子節(jié)點(diǎn)的大小關(guān)系(取決于該堆是大堆還是小堆)

7、pop

//pop - 堆根的數(shù)據(jù)
void HPPop(HP* php)
{//為了不破壞堆的結(jié)構(gòu)，刪除堆根的數(shù)據(jù)，首先讓堆根的數(shù)據(jù)與最后一個(gè)數(shù)據(jù)進(jìn)行交換//然后再使用向下調(diào)整assert(php);Swap(&php->a[0], &php->a[php->size]);//下標(biāo)本身就比實(shí)際個(gè)數(shù)少一AdjustDown(php->a, php->size, 0);//讓堆根的數(shù)據(jù)進(jìn)行向下調(diào)整php->size--;
}

刪除的邏輯？(刪除的是堆根中的數(shù)據(jù))?

如果像順序表中刪除下標(biāo)為0空間中的數(shù)據(jù)邏輯來實(shí)現(xiàn)堆中的刪除 --> 將下標(biāo)為0后面空間中的數(shù)據(jù)向前挪動(dòng)1，以覆蓋下標(biāo)為0空間中的數(shù)據(jù)；由于堆僅僅只是規(guī)定了父子節(jié)點(diǎn)之間的大小關(guān)系，即其兄弟之間并沒有規(guī)定大小關(guān)系；所以當(dāng)數(shù)據(jù)向前挪動(dòng)的時(shí)候父子節(jié)點(diǎn)關(guān)系會(huì)被改變，即父子變兄弟，倘若其父子節(jié)點(diǎn)之間的大小關(guān)系不符合堆的規(guī)定，那么其結(jié)構(gòu)就不能再為堆；也可以重新建堆，但如果每刪除一個(gè)數(shù)據(jù)均要重建堆，這樣的消耗是非常大的；

故而此處采用了另外一個(gè)邏輯，將堆根中的數(shù)據(jù)與數(shù)組中最后一個(gè)數(shù)據(jù)進(jìn)行交換，size--，然后再將堆根上的數(shù)據(jù)進(jìn)行向下調(diào)整(讓根節(jié)點(diǎn)與其子孫進(jìn)行比較，讓根節(jié)點(diǎn)中的數(shù)據(jù)要符合該堆的特點(diǎn))；

8、獲取堆頂數(shù)據(jù)

//獲取堆頂?shù)臄?shù)據(jù)
HPDataType HPTop(HP* php)
{assert(php);assert(php->size);//確保堆中有數(shù)據(jù)可以獲得return php->a[0];
}

9、判空

//判空
bool HPEmpty(HP* php)
{assert(php);//空為真return php->size == 0;
}

(四)、堆排序

1、建堆算法

在講述堆排序之前我們先來了解一下兩種建堆算法；

在上述堆的實(shí)現(xiàn)中，我們利用向上調(diào)整與向下調(diào)整來處理堆中的數(shù)據(jù)，同理我們也可以利用向上調(diào)整或者向下調(diào)整來對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行調(diào)整，讓其成為堆(大堆或者小堆)；

方法一：利用向上調(diào)整建堆

其實(shí)就是模擬上述“堆實(shí)現(xiàn)”中插入push的過程，只不過此處是在原數(shù)組的基礎(chǔ)上進(jìn)行建堆，并沒有另外創(chuàng)建空間來建堆；

代碼如下：

	int arr[] = { 2,10,29,38,42,53,31,4,21 };int sz = sizeof(arr) / sizeof(arr[0]);//建堆 - 向上調(diào)整建堆for (int i = 0; i < sz; i++){AdjustUp(arr, i);}

注：向上調(diào)整算法的復(fù)雜度為O(N^logN);

方法二：利用向下調(diào)整建堆

向上調(diào)整建堆的前提：所調(diào)整的節(jié)點(diǎn)的子樹為堆；

故而想要在數(shù)組中進(jìn)行調(diào)整就不能像上述“堆的實(shí)現(xiàn)”中向上調(diào)整那樣從下標(biāo)為0的數(shù)據(jù)開始調(diào)整；而由于葉節(jié)點(diǎn)沒有孩子，那么可以將葉節(jié)點(diǎn)本身就看做一個(gè)堆，故而向下調(diào)整應(yīng)該從最后一個(gè)非葉節(jié)點(diǎn)開始；

最后一個(gè)非葉節(jié)點(diǎn)如何計(jì)算得到？

• 最后一個(gè)葉結(jié)點(diǎn)的父節(jié)點(diǎn)便是最后一個(gè)非葉結(jié)點(diǎn)；(可利用數(shù)組下標(biāo)進(jìn)行計(jì)算)

代碼如下:

int arr[] = { 2,10,29,38,42,53,31,4,21 };
int sz = sizeof(arr) / sizeof(arr[0]);
//建堆 - 向下調(diào)整建堆
for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(arr, sz, i);
}

注：大堆與小堆中的向上、向下調(diào)整算法有一點(diǎn)差異，具體可以見上面的代碼(堆的實(shí)現(xiàn)中的向上調(diào)整與向下調(diào)整)；

向下調(diào)整算法的時(shí)間復(fù)雜度為:O(N)；

2、堆排序

首先我們先來思考一下倘若我們想要數(shù)組中的數(shù)據(jù)降序，是需要建大堆還是小堆呢？

答案是小堆；因?yàn)槎阎械臄?shù)據(jù)并不是有序的(堆只是規(guī)定了父子節(jié)點(diǎn)的大小關(guān)系，并沒有規(guī)定兄弟節(jié)點(diǎn)之間的大小關(guān)系)，但是堆有個(gè)特點(diǎn)是：大堆中堆根上的數(shù)據(jù)是整個(gè)二叉樹中最大的一個(gè)；小堆中的堆根上的數(shù)據(jù)是整個(gè)二叉樹中最小的一個(gè)；

降序：大數(shù)據(jù)在前面，小數(shù)據(jù)在后面；降序可以有兩種處理方式：

• 一是先確定大數(shù)據(jù)的位置，然后依次確定次大，次次大……的數(shù)據(jù)的位置
• 二是逆向思維，先確定好小數(shù)據(jù)的位置，然后依次確定好次小、次次小……的數(shù)據(jù)的位置；顯然此處最好采用方式二的逆向思維；

我們先來思考一下方式一的問題，倘若排降序而你先確定好大數(shù)據(jù)的位置(大數(shù)據(jù)的對(duì)應(yīng)的空間便不會(huì)再動(dòng)了)，就會(huì)選擇建大堆, 那么抽象地理解上相當(dāng)于頭刪，再將這個(gè)空間后面的數(shù)據(jù)當(dāng)作堆的話又需要重新建堆，因?yàn)榇藭r(shí)父子關(guān)系會(huì)變成兄弟關(guān)系，不符合堆的大小要求，如若每確定一個(gè)數(shù)據(jù)的位置都需要重新建堆的話，這樣的消耗是非常大；此法的時(shí)間復(fù)雜度為：O(N^2 ) (假設(shè)此處建堆采用的是向下調(diào)整建堆，向下調(diào)整建堆的時(shí)間復(fù)雜度為O(N),而有N個(gè)數(shù)據(jù)，所以此算法的時(shí)間復(fù)雜度為：O(N^2)；但是如果建堆采用向上調(diào)整算法的話，那么此法的時(shí)間復(fù)雜度便會(huì)為：O(N^2*logN))；

我們?cè)賮硭伎家幌?strong>方式二的逆向思維，排降序先確定小值的位置，當(dāng)然是建小堆；建小堆，將堆根中的數(shù)據(jù)與數(shù)組中最后一個(gè)數(shù)據(jù)進(jìn)行交換，并且不動(dòng)這個(gè)位置的數(shù)據(jù)(相當(dāng)于尾刪)；交換數(shù)據(jù)并沒有破壞堆根子樹堆的特點(diǎn)，于是可以對(duì)堆根進(jìn)行向下調(diào)整處理，然后重復(fù)上述操作，一個(gè)一個(gè)地確定數(shù)據(jù)地位置讓其變成降序；此法操作的時(shí)間復(fù)雜度為：O(N*logN);

故而排降序需要建小堆；同理，排升序就需要建大堆；

堆排降序的思路：借助于“堆的實(shí)現(xiàn)”中刪除的操作，將堆根中的數(shù)據(jù)與最后一個(gè)數(shù)據(jù)進(jìn)行交換，此時(shí)便會(huì)將該堆中最小的數(shù)據(jù)放在后面，然后進(jìn)行偽刪的操作(“偽刪除，相當(dāng)于不會(huì)將其交換到后面的數(shù)據(jù)當(dāng)作堆中的數(shù)據(jù)”)，然后再進(jìn)行向下調(diào)整；重復(fù)上述操作，最后在數(shù)組中的數(shù)據(jù)便是降序；

代碼如下：

int arr[] = { 2,10,29,38,42,53,31,4,21 };
int sz = sizeof(arr) / sizeof(arr[0]);
//建堆算法兩種均可
//建堆 - 向下調(diào)整建堆 - 排降序 - 建小堆
for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(arr, sz, i);
}建堆 - 向上調(diào)整建堆
//for (int i = 0; i < sz; i++)
//{
//	AdjustUp(arr, i);
//}//排降序
int n = sz - 1;//最后數(shù)據(jù)的下標(biāo)
while (n)//sz 個(gè)數(shù)據(jù)只需要處理 sz-1 次
{//交換Swap(&arr[0], &arr[n]);//偽刪sz--;//向下調(diào)整AdjustDown(arr, sz, 0);n--;
}

注：排升序同理；

(五)、TOP-K 問題

TOP-K問題：求數(shù)據(jù)結(jié)合中前K個(gè)最大的元素的或者最小的元素，一般情況下數(shù)據(jù)量都比較大(千萬、上億級(jí)別)；

例如：世界500強(qiáng)、富豪榜、游戲中的戰(zhàn)力排名等；

我們之前解決最大或者最小的前k個(gè)數(shù)據(jù)的時(shí)候，通常采用排序的方法；但是如果數(shù)據(jù)量非常大(例如 14億)，這時(shí)候如果還使用排序的話，消耗的是非常大的(將數(shù)據(jù)加載到內(nèi)存中的時(shí)間、空間消耗以及排序操作的時(shí)間消耗)，故而此時(shí)會(huì)利用堆來解決數(shù)據(jù)量非常大的TOP-K問題；

假設(shè)此處需要找出14億 人中最有錢的前10個(gè)人；

如果利用上述“堆的實(shí)現(xiàn)”中的思路來解決這個(gè)問題：先建存放了14億個(gè)數(shù)據(jù)的一個(gè)大堆，然后再利用HPTop 與 HPPop 來不斷獲得堆頂?shù)臄?shù)據(jù)；此操作的時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(N)；

假設(shè)一個(gè)數(shù)據(jù)的大小為4byte ,那么存放14億個(gè)數(shù)據(jù)就需要 大約4GB的內(nèi)存空間(小于4GB)；在內(nèi)存中開辟4GB的連續(xù)空間來存放數(shù)據(jù)顯然是不太可能的；

解決方案一：

將總數(shù)據(jù)劃分成若干份(適中)，多次TOP-K即可；

簡(jiǎn)單來說，如果此次所要TOP-K的數(shù)據(jù)有4GB 這么多，那么便先1GB地將數(shù)據(jù)放入內(nèi)存中然后獲取前10個(gè)最大的數(shù)據(jù)……一路下來會(huì)得到40個(gè)最大的數(shù)據(jù)，最后在這40個(gè)數(shù)據(jù)中找到最大的前10個(gè)即可；

當(dāng)然，如果你覺得花1GB的內(nèi)存空間來存放數(shù)據(jù)還是太大了，可以將每一次所要比較的數(shù)再減少一些，這樣每次比較的數(shù)據(jù)便少了，占用的內(nèi)存也小了，但是處理次數(shù)變多了，勢(shì)必會(huì)導(dǎo)致效率下降；(空間換時(shí)間)

解決方案二：

注：假設(shè)此處有100萬個(gè)數(shù)據(jù)存放在文件 "data.txt"? 中

先讀取文件中k個(gè)數(shù)據(jù)以建K個(gè)數(shù)據(jù)的小堆，將文件中的數(shù)據(jù)每次讀一個(gè)放在內(nèi)存中，然后與堆根中的數(shù)據(jù)比較，比堆根的數(shù)據(jù)大便將堆根中的數(shù)據(jù)替換，然后再進(jìn)行向下調(diào)整；

代碼如下：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>//堆的類型聲明
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void CreateData()
{//打開文件 FILE* fin = fopen( "data.txt", "w");if (fin == NULL){perror("fopen");exit(-1);}//產(chǎn)生100萬個(gè)隨機(jī)數(shù)并寫入文件中int n = 1000000;//產(chǎn)生的數(shù)據(jù)個(gè)數(shù)srand((unsigned int)time(NULL));//利用時(shí)間戳產(chǎn)生隨機(jī)的種子for (int i = 0; i < n; i++)//寫入的次數(shù){fprintf(fin, "%d\n", (rand() + i) % 100000000);//產(chǎn)生的數(shù)字范圍0~億}//關(guān)閉文件fclose(fin);fin = NULL;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下調(diào)整算法 - 建小堆
void AdjustDown(HPDataType* a, int n, int parent)
{//利用父節(jié)點(diǎn)的下標(biāo)計(jì)算子節(jié)點(diǎn)的下標(biāo)//假設(shè)法 - 假設(shè)左節(jié)點(diǎn)為較小的結(jié)點(diǎn)int child = parent * 2 + 1;while (child < n)//存在子節(jié)點(diǎn){if (child + 1 < n && a[child + 1] < a[child])//有兩個(gè)孩子的情況下{child++;}//小堆的特征： 父節(jié)點(diǎn) <= 子節(jié)點(diǎn)if (a[parent] > a[child]){Swap(&a[parent], &a[child]);//調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}}void TOP_KHeap()
{int k = 0;printf("請(qǐng)輸入k：>");scanf("%d", &k);//動(dòng)態(tài)開辟一個(gè)數(shù)組的空間 - 建小堆的準(zhǔn)備工作HPDataType* KminHeap = (HPDataType*)malloc(k*sizeof(HPDataType));if (KminHeap == NULL){perror("TOP_KHeap malloc");exit(-1);}//打開文件FILE * fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen");exit(-1);}//操作//先從文件中讀取k個(gè)數(shù)據(jù) - 放入創(chuàng)建的數(shù)組中for (int i = 0; i < k; i++){fscanf(fout, "%d", &KminHeap[i]);}//建小堆 - 向下調(diào)整與向上調(diào)整均可for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(KminHeap, k , i);}//讀取文件中剩余的數(shù)據(jù)int x = 0;//一個(gè)一個(gè)地讀，存放在變量x 中while (fscanf(fout, "%d", &x) != EOF){if (x > KminHeap[0]){//直接覆蓋,再向下調(diào)整KminHeap[0] = x;AdjustDown(KminHeap, k, 0);}}//此時(shí)，數(shù)組KminHeap 中的k個(gè)數(shù)據(jù)為文件data.txt 中最大的前k 個(gè)數(shù)據(jù)；printf("最大的前%d個(gè)數(shù)據(jù)：", k);for (int i = 0; i < k; i++){printf("%d ", KminHeap[i]);}printf("\n");//換行//關(guān)閉文件fclose(fout);fout = NULL;
}

分析：

1、造100萬個(gè)隨機(jī)數(shù)部分：

srand 與 rand 常一起使用，srand 可以利用時(shí)間戳而產(chǎn)生不同的"種子"（偽隨機(jī)數(shù)）而 讓rand 每次產(chǎn)生的隨機(jī)數(shù)都不太一樣；int 可存放的數(shù)據(jù)范圍為 0~?2147483647; 故而在生成隨機(jī)數(shù)最好控制在0~億之內(nèi)，即(rand() + i)%100000000 , 因?yàn)?span style="background-color:#cccccc;">rand() 產(chǎn)生的數(shù)據(jù)額范圍為0~32767 ， +i 是為了避免產(chǎn)生許多重復(fù)的數(shù)，，%100000000 是為了控制產(chǎn)生的隨機(jī)數(shù)的范圍避免溢出，減少重復(fù)值；

打開文件 - 操作文件(將產(chǎn)生的隨機(jī)值放到文件中) - 關(guān)閉文件

2、TOP-K問題的解決

主邏輯：建小堆，讓數(shù)據(jù)與堆根中的數(shù)據(jù)進(jìn)行比較(小堆中堆根的數(shù)據(jù)為此堆中最小的數(shù)據(jù))，如果文件有數(shù)據(jù)比堆根中的數(shù)據(jù)大，便讓此數(shù)據(jù)替換堆根中的數(shù)據(jù)再進(jìn)行向下調(diào)整，如此重復(fù)下去，直到文件中的數(shù)據(jù)讀取結(jié)束；

整體邏輯梳理：

• 1、變量的準(zhǔn)備：k、存放k 個(gè)數(shù)據(jù)的數(shù)組(所要進(jìn)行建小堆的數(shù)據(jù))

此處建立存放k個(gè)數(shù)據(jù)的數(shù)組的空間是使用malloc 動(dòng)態(tài)開辟的；原因：k 為變量，在VS編譯器中不支持變長(zhǎng)數(shù)組；

• 2、打開文件 - 讀取100萬個(gè)數(shù)據(jù)
• 3、操作文件?

先將文件中的前k個(gè)數(shù)據(jù)讀取放入數(shù)組KminHeap 中，然后以向下調(diào)整的方式建小堆(當(dāng)然，也可以使用向上調(diào)整算法，推薦使用向下調(diào)整算法，因?yàn)橄蛳抡{(diào)整建堆算法的時(shí)間復(fù)雜度更優(yōu))，然后再將剩余的數(shù)據(jù)一個(gè)一個(gè)地讀取放在變量x 中，再與堆根中 的數(shù)據(jù)進(jìn)行比較，大于堆根中 的數(shù)據(jù)便將此數(shù)替換堆根中的數(shù)據(jù)；如此往復(fù)，直至文件中的數(shù)據(jù)讀取完了；

此處利用fscanf 來讀取文件中 的數(shù)據(jù)，當(dāng)fscanf 讀取失敗即返回EOF，此時(shí)便代表著文件中的數(shù)據(jù)均讀取完了；

當(dāng)文件中的數(shù)據(jù)均讀完的時(shí)候，此時(shí)KminHeap 中k 個(gè)數(shù)據(jù)，便是這個(gè)文件中100萬個(gè)數(shù)據(jù)中最大的前K個(gè)；

• 4、關(guān)閉文件

注：細(xì)節(jié)：由于我們?cè)趯懭腚S機(jī)數(shù)到文件中的時(shí)候，數(shù)據(jù)本身是用'\n' 來分割的；而fscanf 在讀取數(shù)據(jù)的時(shí)候遇到空格或者換行本身就會(huì)終止(scanf 遇到空格或者換行(空白字符) 便會(huì)以為是數(shù)據(jù)個(gè)數(shù)的分割)，故而在讀取數(shù)據(jù)的時(shí)候直接寫作：fscanf(fout, "%d", &x)? 即可，不用在%d 后面再增加'\n' ;

總結(jié)

1、樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n (n>=0) 個(gè)有限結(jié)點(diǎn)組成的具有層次關(guān)系的集合，將此結(jié)構(gòu)叫做樹的原因是因?yàn)榇私Y(jié)構(gòu)像一棵倒掛的樹，即其根在上，而葉朝下；

2、二叉樹(Binary Tree) 是n (n>=0) 個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集(即空二叉樹)，或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹構(gòu)成，

3、堆是一種數(shù)據(jù)結(jié)構(gòu)，可以在其中插入、刪除數(shù)據(jù)，讓其結(jié)構(gòu)仍為堆；利用堆來進(jìn)行選數(shù)是非常方便的，不用我們自己去建堆、調(diào)整。(注：以后在c++中還有一種數(shù)據(jù)結(jié)構(gòu)叫做 優(yōu)先級(jí)隊(duì)列)

4、堆可以用來進(jìn)行排序；堆排序是在堆這個(gè)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上利用向上調(diào)整或者向下調(diào)整來建堆的(直接對(duì)數(shù)組進(jìn)行建堆操作)

5、TOP-K問題；

解決TOP-K問題有兩種方式：

• 1、數(shù)據(jù)量不大，直接建大堆、pop數(shù)據(jù)便可；此法的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)
• 2、數(shù)據(jù)量很大的時(shí)候，需要建立一個(gè)K個(gè)數(shù)的小堆，讓(文件中)的數(shù)據(jù)與堆根中 的數(shù)據(jù)進(jìn)行比較，比堆根大便進(jìn)行交換(實(shí)際上是直接將堆根中的數(shù)據(jù)進(jìn)行覆蓋)，然后再向下調(diào)整；此法的時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(1)；

注：方法二與方法一在效率上是差不多的，但是方法二更節(jié)約空間；

6、我們之前學(xué)習(xí)的時(shí)間復(fù)雜度就是純粹地將數(shù)據(jù)存放起來。只不過在存儲(chǔ)地時(shí)候，例如數(shù)組、鏈表這樣的結(jié)構(gòu)，它們各有優(yōu)勢(shì)；而堆這種數(shù)據(jù)結(jié)構(gòu)并不是單純地用來存放數(shù)據(jù)，更重要的是利用堆存放數(shù)據(jù)可以幫助我們更加高效地進(jìn)行排序、解決TOP-K問題等，即堆這種數(shù)據(jù)結(jié)構(gòu)帶有一定的功能性；

堆借助于完全二叉樹的特性(高度低而可以存放大量的數(shù)據(jù))，那么向上調(diào)整、向下調(diào)整的次數(shù)就比較少，效率也就高(可以高效地幫助我們?nèi)ミx數(shù)來解決生活中地問題)；