堆

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

1. 樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?#xff0c;也就是說它是根朝上，而葉朝下的。

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

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

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

• 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子樹的個(gè)數(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)：若一個(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）棵互不相交的樹的集合稱為森林；

3. 樹的表示

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

typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一個(gè)孩子結(jié)點(diǎn)struct Node* pNextBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn)DataType data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

4. 樹在實(shí)際中的運(yùn)用（表示文件系統(tǒng)的目錄樹結(jié)構(gòu)）

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

1. 概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合:

1. 或者為空
2. 由一個(gè)根結(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成
   

從上圖可以看出：

1. 二叉樹不存在度大于2的結(jié)點(diǎn)
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
   注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：
   

2. 特殊的二叉樹

1. 滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是$2^k?1$ ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
   

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

1. 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第$i$層上最多有$2^{(i?1)}$個(gè)結(jié)點(diǎn).
2. 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則深度為$h$的二叉樹的最大結(jié)點(diǎn)數(shù)是$2^h?1$.
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為$n_0$, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為$n_2$,則有$n_0＝n_2＋1$

/*
* 假設(shè)二叉樹有N個(gè)結(jié)點(diǎn)
* 從總結(jié)點(diǎn)數(shù)角度考慮：N = n0 + n1 + n2 ①
*
* 從邊的角度考慮，N個(gè)結(jié)點(diǎn)的任意二叉樹，總共有N-1條邊
* 因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)都有雙親，根結(jié)點(diǎn)沒有雙親，每個(gè)節(jié)點(diǎn)向上與其雙親之間存在一條邊
* 因此N個(gè)結(jié)點(diǎn)的二叉樹總共有N-1條邊
* 因?yàn)槎葹?的結(jié)點(diǎn)沒有孩子，故度為0的結(jié)點(diǎn)不產(chǎn)生邊; 度為1的結(jié)點(diǎn)只有一個(gè)孩子，故每個(gè)度
* 為1的結(jié)點(diǎn)產(chǎn)生一條邊; 度為2的結(jié)點(diǎn)有2個(gè)孩子，故每個(gè)度為2的結(jié)點(diǎn)產(chǎn)生兩條邊，所以總邊
* 為：n1+2*n2
* 故從邊的角度考慮：N-1 = n1 + 2*n2 ②
* 結(jié)合① 和 ②得：n0 + n1 + n2 = n1 + 2*n2 - 1
* 即：n0 = n2 + 1
*/

4. 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，$h=lo{g}_2(n+1)$. (ps： $h=lo{g}_2(n+1)$是log以2為底，n+1為對數(shù))
5. 對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ薪Y(jié)點(diǎn)從0開始編號，則對于序號為i的結(jié)點(diǎn)有：

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

1. 某二叉樹共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ ）
   A 不存在這樣的二叉樹
   B 200
   C 198
   D 199
2. 下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲(chǔ)結(jié)構(gòu)的是（ ）
   A 非完全二叉樹
   B 堆
   C 隊(duì)列
   D 棧
3. 在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（ ）
   A n
   B n+1
   C n-1
   D n/2
4. 一棵完全二叉樹的結(jié)點(diǎn)數(shù)位為531個(gè)，那么這棵樹的高度為（ ）
   A 11
   B 10
   C 8
   D 12
5. 一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為（）
   A 383
   B 384
   C 385
   D 386

答案：
1.B
2.A
3.A
4.B
5.B

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

二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

1. 順序存儲(chǔ)
   順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來存儲(chǔ)，關(guān)于堆我們后面的章節(jié)會(huì)專門講解。二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。
   

2. 鏈?zhǔn)酱鎯?chǔ)
   二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，后面學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會(huì)用到三叉鏈。
   

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{struct BinTreeNode* left; // 指向當(dāng)前結(jié)點(diǎn)左孩子struct BinTreeNode* right; // 指向當(dāng)前結(jié)點(diǎn)右孩子BTDataType data; // 當(dāng)前結(jié)點(diǎn)值域
}
// 三叉鏈
struct BinaryTreeNode
{struct BinTreeNode* parent; // 指向當(dāng)前結(jié)點(diǎn)的雙親struct BinTreeNode* left; // 指向當(dāng)前結(jié)點(diǎn)左孩子struct BinTreeNode* right; // 指向當(dāng)前結(jié)點(diǎn)右孩子BTDataType data; // 當(dāng)前結(jié)點(diǎn)值域
}；

三. 二叉樹的順序結(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)

如果有一個(gè)關(guān)鍵碼的集合K = { $k_0$， $k_1$， $k_2$，…， $k_{n?1}$}，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足： $k_i<=k_{2i+1}$ 且 $k_i<=k_{2i+2}$ ($k_i>=k_{2i+1}$ 且 $k_i>=k_{2i+2}$ ) i = 0，1，2…，則稱為小堆(或大堆)。將根結(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根結(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

• 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
• 堆總是一棵完全二叉樹

3. 建堆時(shí)間復(fù)雜度

因?yàn)槎咽峭耆鏄?#xff0c;而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時(shí)間復(fù)雜度本來看的就是近似值，多幾個(gè)結(jié)點(diǎn)不影響最終結(jié)果)：

因此：建堆的時(shí)間復(fù)雜度為O(N)。

選擇題
1.下列關(guān)鍵字序列為堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32
2.已知小根堆為8,15,10,21,34,16,12，刪除關(guān)鍵字 8 之后需重建堆，在此過程中，關(guān)鍵字之間的比較次數(shù)是（）。
A 1
B 2
C 3
D 4
3.一組記錄排序碼為(5 11 7 2 3 17),則利用堆排序方法建立的初始堆為
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
4.最小堆[0,3,2,5,7,4,6,8],在刪除堆頂元素0之后，其結(jié)果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]

選擇題答案

1. A
2. C
3. C
4. C

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

typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的構(gòu)建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(Heap* hp);
// 堆的數(shù)據(jù)個(gè)數(shù)
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

4.1 結(jié)構(gòu)體部分

堆的實(shí)現(xiàn)我們按照動(dòng)態(tài)順序表為物理結(jié)構(gòu)（即順序存儲(chǔ)結(jié)構(gòu)），以完全二叉樹為邏輯結(jié)構(gòu)。

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

4.2 初始化 HPInit

下面我們給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個(gè)堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個(gè)堆。根結(jié)點(diǎn)左右子樹不是堆，我們怎么調(diào)整呢？這里我們從倒數(shù)的第一個(gè)非葉子結(jié)點(diǎn)的子樹開始調(diào)整，一直調(diào)整到根結(jié)點(diǎn)的樹，就可以調(diào)整成堆。

int a[] = {1,5,3,8,7,6};

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

4.3 銷毀 HPDestroy

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

4.4 交換 Swap

這里我們實(shí)現(xiàn)一個(gè)交換函數(shù)，方便我們后續(xù)對堆的元素進(jìn)行調(diào)整。

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

4.5 堆的插入 HPPush

先插入一個(gè)10到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆。

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* newa = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (newa == NULL){perror("realloc failed!\n");exit(1);}php->a = newa;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

現(xiàn)在，我們只是把一個(gè)元素插入到了數(shù)組之中，接下來，我們要對該元素進(jìn)行向上調(diào)整。

4.6 堆底元素向上調(diào)整 AdjustUp

void AdjustUp(HPDataType* a, int child)//向上調(diào)整
{int parent = (child - 1) / 2;//小堆//while (parent >= 0)while(child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//交換child = parent;parent = (child - 1) / 2;}else{break;}}
}

4.7 堆的刪除 HPPop

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。

//時(shí)間復(fù)雜度：O(logN)
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);
}

現(xiàn)在，我們也同樣只是把堆頂元素（根位置元素）從數(shù)組中刪除，接下來的向下調(diào)整算法，才是堆的核心算法，也是堆排序的核心算法。

4.8 堆頂元素向下調(diào)整算法 AdjustDown

現(xiàn)在我們給出一個(gè)數(shù)組，邏輯上看做一顆完全二叉樹。我們通過從根結(jié)點(diǎn)開始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆。向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

void AdjustDown(HPDataType* a,int n, int parent)//堆頂元素向下調(diào)整
{//假設(shè)左孩子小int child = parent * 2 + 1;while (child < n)//如果child >= n，說明孩子不存在，調(diào)整到葉子了{//找出小的那個(gè)孩子if (child + 1 < n && a[child + 1] < a[child])//防止越界{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

4.9 返回堆頂元素 HPTop

HPDataType HPTop(HP* php)
{assert(php);return php->a[0];
}

4.10 判空 HPEmpty

_Bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

4.11 堆排序 HeapSort

void HeapSort(HPDataType* a, int n)
{//建堆//降序 -- 建小堆//升序 -- 建大堆//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//建堆//從最后一個(gè)父親節(jié)點(diǎn)開始，依次向上執(zhí)行向下調(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]);//將排列好的元素放在最后面AdjustDown(a, end, 0);--end;}
}

5. 堆的應(yīng)用

5.1 堆排序

堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個(gè)步驟：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆刪除思想來進(jìn)行排序
   建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。

5.2 TOP-K問題

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：

1. 用數(shù)據(jù)集合中前K個(gè)元素來建堆
   前k個(gè)最大的元素，則建小堆
   前k個(gè)最小的元素，則建大堆
2. 用剩余的N-K個(gè)元素依次與堆頂元素來比較，不滿足則替換堆頂元素
   將剩余N-K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。

void PrintTopK(int* a, int n, int k)
{// 1. 建堆--用a中前k個(gè)元素建堆// 2. 將剩余n-k個(gè)元素依次與堆頂元素交換，不滿則則替換int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}// 讀取數(shù)組中前k個(gè)數(shù)for (int i = 0; i < k; i++){kminheap[i] = a[i];}// 建K個(gè)數(shù)的小堆for (int i = (k-1-1)/2; i>=0 ; i--){AdjustDown(kminheap, k, i);}// 讀取剩下的N-K個(gè)數(shù)int x = k;while (x < n){if (x > kminheap[0]){kminheap[0] = x;AdjustDown(kminheap, k, 0);}}printf("最大前%d個(gè)數(shù)：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}void TestTopk()
{int n = 10000;int* a = (int*)malloc(sizeof(int)*n);srand(time(0));//造數(shù)據(jù)for (size_t i = 0; i < n; ++i){a[i] = rand() % 1000000;}//人為創(chuàng)造最大的大數(shù)a[5] = 1000000 + 1;a[1231] = 1000000 + 2;a[531] = 1000000 + 3;a[5121] = 1000000 + 4;a[115] = 1000000 + 5;a[2335] = 1000000 + 6;a[9999] = 1000000 + 7;a[76] = 1000000 + 8;a[423] = 1000000 + 9;a[3144] = 1000000 + 10;PrintTopK(a, n, 10);
}

四. 參考代碼

Heap.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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);//插入數(shù)據(jù)
void HPPush(HP* php, HPDataType x);//刪除堆頂元素（根位置）
void HPPop(HP* php);//返回堆頂元素
HPDataType HPTop(HP* php);//判空
_Bool HPEmpty(HP* php);//堆底元素向上調(diào)整
void AdjustUp(HPDataType* a, int child);//堆頂元素向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent);//交換
void Swap(HPDataType* p1, HPDataType* p2);

Heap.c

#include "Heap.h"void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)//向上調(diào)整
{int parent = (child - 1) / 2;//小堆//while (parent >= 0)while(child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//交換child = parent;parent = (child - 1) / 2;}else{break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* newa = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (newa == NULL){perror("realloc failed!\n");exit(1);}php->a = newa;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}void AdjustDown(HPDataType* a,int n, int parent)//堆頂元素向下調(diào)整
{//假設(shè)左孩子小int child = parent * 2 + 1;while (child < n)//如果child >= n，說明孩子不存在，調(diào)整到葉子了{//找出小的那個(gè)孩子if (child + 1 < n && a[child + 1] < a[child])//防止越界{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//時(shí)間復(fù)雜度：O(logN)
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);
}HPDataType HPTop(HP* php)
{assert(php);return php->a[0];
}_Bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

test.c

#include "Heap.h"
#include "vld.h"void TestHeap01()
{int a[10] = { 2,3,4,1,6,5,9,8,7,0 };HP hp;HPInit(&hp);size_t sz = sizeof(a) / sizeof(int);for (size_t i = 0; i < sz; i++){HPPush(&hp, a[i]);}int i = 0;while (!HPEmpty(&hp)){//printf("%d ", HPTop(&hp));a[i++] = HPTop(&hp);HPPop(&hp);}HPDestroy(&hp);
}void HeapSort(HPDataType* a, int n)
{//建堆//降序 -- 建小堆//升序 -- 建大堆//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//建堆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]);AdjustDown(a, end, 0);--end;}
}//排序
//void HeapSort(HPDataType* a, int n);void TestHeap02()
{int a[10] = { 2,3,4,1,6,5,9,8,7,0 };size_t sz = sizeof(a) / sizeof(int);HeapSort(a, sz);for (int i = 0; i < sz; i++){printf("%d ", a[i]);}printf("\n");}int main()
{//TestHeap01();TestHeap02();return 0;
}