歡迎來到 Claffic 的博客???????
“春風(fēng)里，是誰 花一樣爛漫？”
前言：
二叉樹給大家講解的差不多了，接下來就是二叉樹的實際應(yīng)用了：這期我們來講堆，它是一種順序結(jié)構(gòu)的特殊二叉樹，可以實現(xiàn)排序等功能，那就讓我們開始吧！
目錄
??Part1: 何為堆
1.堆的概念
2.堆的結(jié)構(gòu)
??Part2: 堆的實現(xiàn)?
1.前期準(zhǔn)備
1.1項目創(chuàng)建
1.2結(jié)構(gòu)定義
1.3堆的初始化
2.相關(guān)功能實現(xiàn)
2.1堆插入數(shù)據(jù)
2.2堆刪除數(shù)據(jù)?
2.3數(shù)組建堆
2.4判斷堆是否為空
2.5獲取堆頂元素
2.6堆的銷毀
??Part3: 堆的應(yīng)用
3.1堆排序（排升序）
3.2 TOP-K問題
Part1: 何為堆
1.堆的概念
將元素按照完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足對應(yīng)根結(jié)點數(shù)值大于兩個孩子結(jié)點（稱為大堆）或者小于兩個孩子結(jié)點（稱為小堆）。
單看概念是不足以理解的，與結(jié)構(gòu)結(jié)合理解會更好：
2.堆的結(jié)構(gòu)
還記得上期的 邏輯結(jié)構(gòu) 和 物理結(jié)構(gòu) 嗎？
堆的邏輯結(jié)構(gòu)是一顆 完全二叉樹?
堆的本質(zhì)呢，是 數(shù)組 ，不過對數(shù)組中存儲的數(shù)據(jù)順序有著特殊的要求：?
? 大堆：根節(jié)點數(shù)值大于兩個孩子結(jié)點的數(shù)值；
? 小堆：根節(jié)點數(shù)值小于兩個孩子結(jié)點的數(shù)值。
上例子：?
這是一個大堆
這是一個小堆
到這里，相信你已經(jīng)知道什么是堆了。
記住堆的性質(zhì)：
? 堆總是一顆完全二叉樹
? 堆中某個結(jié)點的數(shù)值總是不大于或不小于雙親結(jié)點
Part2: 堆的實現(xiàn)?
1.前期準(zhǔn)備
1.1項目創(chuàng)建
Heap.h：頭文件，聲明所有函數(shù)；
Heap.c：源文件，實現(xiàn)各函數(shù)；
Test.c：??源文件，主函數(shù)所在項，可調(diào)用各函數(shù)。
1.2結(jié)構(gòu)定義
堆的本質(zhì)就是一個數(shù)組嘛，
默認(rèn)整型數(shù)組，為方便相關(guān)操作的實現(xiàn)，再定義大小size和容量capacity：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
1.3堆的初始化
這里選擇動態(tài)開辟內(nèi)存，
初始容量為4個整型大?。?
//堆的初始化
void HeapInit(HP* php)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
php->capacity = 4;
php->size = 0;
}
2.相關(guān)功能實現(xiàn)
注意：我們這里默認(rèn)實現(xiàn)大堆?
2.1堆插入數(shù)據(jù)
插入數(shù)據(jù)前，要先判斷下有沒有滿，定義容量和大小的好處就在這里，
直接通過 容量和大小是否相等 就可以，
如果滿，默認(rèn)擴展至先前容量的兩倍；
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity*2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;接下來就是對插入的數(shù)據(jù)進行調(diào)整了，
要注意：插入之前就是大堆或小堆（默認(rèn)大堆），
我們需要做的就是將插在末尾的數(shù)據(jù)通過比較交換，使其在最合適的位置
這里用到的是 向上調(diào)整 ：
第一次做這種動圖??????
如圖所示，在數(shù)組末尾插入數(shù)據(jù)后，需要跟雙親結(jié)點比較，再決定是否向上調(diào)整。
//向上調(diào)整
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 = (child - 1) / 2;
}
else
break;
}
}
?所以最終代碼：
//堆插入數(shù)據(jù) 向上調(diào)整 插入之前就是堆
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity*2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
2.2堆刪除數(shù)據(jù)?
大堆刪除數(shù)據(jù)，是指刪除 最大根節(jié)點 。
那么怎樣才能保證刪除第一個數(shù)據(jù)之后，剩余的結(jié)點的雙親結(jié)點與孩子結(jié)點關(guān)系不亂呢？?
這里有一個巧妙的辦法：?
先將第一個結(jié)點與最后一個結(jié)點 交換 ，再 刪除 最后一個結(jié)點，最后 向下調(diào)整 。
最后仍然保持是一個大堆
代碼實現(xiàn)：
//堆刪除數(shù)據(jù) 向下調(diào)整
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);
}
//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//先判斷child，防止越界，挑出較大的孩子結(jié)點
if (child < n + 1 && a[child + 1] < a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
2.3數(shù)組建堆
任意給一個數(shù)組，可不能保證它就是堆，
所以要利用數(shù)組來建堆，也叫用數(shù)組初始化堆。
前半部分的空間開辟不必多講，重點放在建堆（默認(rèn)建大堆）上：
方法一：向上調(diào)整
給一個數(shù)組，先從第一個數(shù)開始，逐漸擴大區(qū)間，每擴大一次就進行一次向上調(diào)整；
其實就是 模擬插入數(shù)值 罷了。
//建堆（默認(rèn)建大堆），向上調(diào)整
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
方法二：向下調(diào)整
這種方法是從倒數(shù)第二層數(shù)組開始調(diào)整，依次向下調(diào)整。
//建堆，向下調(diào)整
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
兩種方法對比：?
這里先告訴大家結(jié)論：
向下調(diào)整建堆（時間復(fù)雜度為：O(N)）要優(yōu)于向上調(diào)整建堆（時間復(fù)雜度為：O(N*logN)）
準(zhǔn)確計算方式：其實就是每層的結(jié)點個數(shù)乘以要向下/向上調(diào)整的層數(shù)，最后求和，比較下即可。
簡單理解：
向下調(diào)整：結(jié)點多的調(diào)整次數(shù)少，結(jié)點少的調(diào)整次數(shù)多；
向上調(diào)整：結(jié)點少的調(diào)整次數(shù)少，結(jié)點多的調(diào)整次數(shù)多；
就這個描述，向下調(diào)整更平衡一些，在這種粗略理解下，向下調(diào)整優(yōu)于向上調(diào)整。
2.4判斷堆是否為空
直接判斷大小是否為0即可。
//判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
2.5獲取堆頂元素
返回數(shù)組的第一個值即可。
//獲取堆頂元素
HPDataType HeapTop(HP* php)
{
assert(php);
return php->a[0];
}
2.6堆的銷毀
將數(shù)組釋放置空，容量和大小歸零。?
//堆的銷毀
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
Part3: 堆的應(yīng)用
3.1堆排序（排升序）
給你一個數(shù)組，要進行堆排序，首先要把它 變成堆 ，
考慮下這個問題：排升序，建大堆還是小堆？
答案是 建大堆 ，
因為大堆的最大根節(jié)點就是整個堆中最大的，我們只需要將這個最大值調(diào)整到最后就可以了；
如果是小堆，我們不能保證兩個孩子結(jié)點的大小關(guān)系，調(diào)整起來就比大堆麻煩。
再者就是優(yōu)先選擇 向下調(diào)整 ，效率較高。
//向下調(diào)整（效率更高）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}建完大堆，接下來就是數(shù)據(jù)位置的調(diào)整了：?
將最大根節(jié)點調(diào)整到最后，然后通過調(diào)整，保持剩余結(jié)點依然是一個大堆。
是不是感覺與刪除操作有些相似？
是的，這可以理解為 模擬刪除操作 ，只不過被刪除的數(shù)還是要保留的。
最終代碼：
//堆排序
void HeapSort(int* a, int n)
{
//向下調(diào)整（效率更高）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end--)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
}
}3.2 TOP-K問題
給一個情景：
在世界所有的企業(yè)中選出世界500強。
這就涉及到TOP-K問題，簡單理解，TOP-K問題就是在N個數(shù)字中選出K個數(shù)字，保證這K個數(shù)字任何一個都比剩余N-K個數(shù)字大。
建堆是必須的，但建大堆還是小堆？
這里有一個巧妙的辦法：
1.前K個數(shù)字先建成一個小堆；
2.遍歷剩余N-K個數(shù)字，遇到比堆頂數(shù)字大的就替它進堆，再進行向下調(diào)整。
這種方法巧妙在 大數(shù)向下沉，小數(shù)向上浮。最后大數(shù)把小數(shù)擠出堆，堆里的都是大數(shù)。
為了創(chuàng)建大量數(shù)據(jù)，這里利用隨機數(shù)，將數(shù)據(jù)存儲在文件當(dāng)中：
void PrintTopK(const char* file, int k)
{
// 用a中前k個元素建小堆
int* topk = (int*)malloc(sizeof(int) * k);
assert(topk);
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &topk[i]);
}
for (int i = (k - 2) / 2; i >= 0; --i)
{
AdjustDown(topk, k, i);
}
// 將剩余n-k個元素依次與堆頂元素交換，不滿就替換
int val = 0;
int ret = fscanf(fout, "%d", &val);
while (ret != EOF)
{
if (val > topk[0])
{
topk[0] = val;
AdjustDown(topk, k, 0);
}
ret = fscanf(fout, "%d", &val);
}
for (int i = 0; i < k; i++)
{
printf("%d ", topk[i]);
}
printf("\n");
free(topk);
fclose(fout);
}?
代碼已上傳至?我的gitee
拿走不謝~?
總結(jié)：
這期知識密度較大，不僅有堆的實現(xiàn)，還有兩個堆的應(yīng)用，建議先將堆實現(xiàn)一波，再進行兩個應(yīng)用問題的解決~~~
碼文不易?文章來源：http://www.zghlxwxcb.cn/news/detail-409957.html
如果你覺得這篇文章還不錯并且對你有幫助，不妨支持一波哦????????文章來源地址http://www.zghlxwxcb.cn/news/detail-409957.html
到了這里，關(guān)于什么是堆，如何實現(xiàn)？(附堆排序，TOP-K問題)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
