前言：在二叉樹基礎(chǔ)篇我們提到了二叉樹的順序?qū)崿F(xiàn)，今天讓我們來學(xué)習(xí)一下特殊的二叉樹———堆的相關(guān)知識(shí)。
??博客主頁： 小鎮(zhèn)敲碼人
??熱門專欄：數(shù)據(jù)結(jié)構(gòu)與算法
?? 歡迎關(guān)注：??點(diǎn)贊 ????留言 ??收藏
?? 任爾江湖滿血骨，我自踏雪尋梅香。 萬千浮云遮碧月，獨(dú)傲天下百堅(jiān)強(qiáng)。 男兒應(yīng)有龍騰志，蓋世一意轉(zhuǎn)洪荒。 莫使此生無痕度，終歸人間一捧黃。??????
?? 什么？你問我答案，少年你看，下一個(gè)十年又來了 ?? ?? ??
?? 堆的概念
堆是一種完全二叉樹，但是其節(jié)點(diǎn)值滿足一些特定的規(guī)則，又分為小堆和大堆，小堆是任意根節(jié)點(diǎn)的值都小于等于它子樹的節(jié)點(diǎn)值，大堆是任意根節(jié)點(diǎn)的值都大于等于它子樹的值。
小堆：
大堆：
注意：不管是大堆還是小堆，其同一層的節(jié)點(diǎn)大小可任意。
?? 堆的模擬實(shí)現(xiàn)
?? 堆的結(jié)構(gòu)和方法接口
在二叉樹部分我們?cè)?jīng)提到，堆是一種完全二叉樹，所以其使用順序存儲(chǔ)是不會(huì)浪費(fèi)空間的，而順序存儲(chǔ)就是我們常說的動(dòng)態(tài)順序表。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
//堆的初始化
void HeapInit(Heap* hp);
// 堆的構(gòu)建(直接給一個(gè)數(shù)組)
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);
//向上調(diào)整建堆
void AdjustUp(HPDataType* a, int child);
//向下調(diào)整
void AdjustDown(HPDataType* a, int parent, int n);
//兩數(shù)交換
void Swap(HPDataType* hp1, HPDataType* hp2);
//打印堆
void HeapPrint(Heap* hp);
//堆排序
void Heapsort(HPDataType* a, int n);
?? 堆的方法的模擬實(shí)現(xiàn)
下面我們的方法我們都默認(rèn)建一個(gè)小堆。
?? 堆的初始化
堆的初始化很簡單，我們將其對(duì)應(yīng)的指針置空，元素個(gè)數(shù)和空間大小置0即可。
//堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);//hp不為空
hp->_a = NULL;//指針置為空
hp->_capacity = hp->_size = 0;//元素和空間大小置為0
}
?? 堆的構(gòu)建
給你一個(gè)數(shù)組，你應(yīng)該如何建一個(gè)小堆呢？我們來畫圖分析：
// 堆的構(gòu)建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);//斷言，防止hp為空
hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);//為存節(jié)點(diǎn)的數(shù)組申請(qǐng)空間
hp->_size = hp->_capacity = n;//更新空間大小和元素大小
memcpy(hp->_a, a, sizeof(HPDataType) * n);//將數(shù)組里的值copy到我們的數(shù)據(jù)域里面
//向上調(diào)整建一個(gè)小堆
for (int i = 1; i < n; i++)
{
AdjustUp(hp->_a,i);
}
}
圖解代碼：
向下調(diào)整建堆的時(shí)間復(fù)雜度分析：
?? 堆的插入
堆的插入應(yīng)該如何實(shí)現(xiàn)呢?我們直接插入到線性表尾部就行，由于插入前是堆，所以我們走一個(gè)向上調(diào)整就可以將其調(diào)整為堆。
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);//斷言，防止hp為空
if (hp->_size == hp->_capacity)//擴(kuò)容
{
hp->_capacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * hp->_capacity);
if (tmp == NULL)
{
perror("realloc failed\n");
exit(-1);
}
hp->_a = tmp;
}
hp->_a[hp->_size] = x;//插入
hp->_size++;
//向上調(diào)整
AdjustUp(hp->_a,hp->_size - 1);//在插入位置走一個(gè)向上調(diào)整
}
?? 向上調(diào)整
上面已經(jīng)分析過了。
//向上調(diào)整建小堆
void AdjustUp(HPDataType* a, int child)
{
assert(a);//a不為空
int parent = (child - 1) / 2;//找到child的父親節(jié)點(diǎn)，和其比較看是否需要調(diào)整
while (child > 0)
{
if (a[child] < a[parent])//建一個(gè)小堆，如果孩子節(jié)點(diǎn)比父親節(jié)點(diǎn)的值小，需要調(diào)整
{
Swap(&a[child], &a[parent]);//交換
child = parent;//將父親節(jié)點(diǎn)的值給孩子，繼續(xù)在這條路徑上調(diào)整
parent = (parent - 1) / 2;//更新父親節(jié)點(diǎn)的下標(biāo)
}
else
{
break;//孩子節(jié)點(diǎn)的值已經(jīng)大于等于父親節(jié)點(diǎn)的值了，不需要再繼續(xù)調(diào)整
}
}
}
?? 堆的刪除
堆的刪除我們是刪除堆頂?shù)臄?shù)據(jù)，因?yàn)檫@個(gè)數(shù)據(jù)最值得去刪，什么意思呢？舉個(gè)例子1.因?yàn)閯h除最后一個(gè)節(jié)點(diǎn)不會(huì)改變堆的結(jié)構(gòu)沒什么意義，2.堆頂數(shù)據(jù)要么是最大值，要么是最小值，很特殊。
那我們應(yīng)該如何實(shí)現(xiàn)堆的刪除呢？我們還是畫圖來分析：
代碼實(shí)現(xiàn)：
// 堆的刪除
void HeapPop(Heap* hp)
{
assert(hp);//hp不為空
assert(hp->_size > 0);//堆的元素個(gè)數(shù)要大于0
Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//交換堆頂元素和最后一個(gè)元素的值
hp->_size--;//_size--
//向下調(diào)整
AdjustDown(hp->_a, 0, hp->_size);//根節(jié)點(diǎn)左樹和右樹為小堆，可以向下調(diào)整
}
?? 向下調(diào)整
這個(gè)我們上面也已經(jīng)分析了，直接給代碼：
//向下調(diào)整(小堆)
void AdjustDown(HPDataType* a, int parent, int n)
{
assert(a);//a不為空
int child = parent * 2 + 1;//先假設(shè)最小的孩子是左孩子
while (child < n)
{
//找出最小的孩子
if (child+1 < n && a[child] > a[child + 1])//如果右孩子存在且右孩子的值比左孩子更小
{
child = child + 1;
}
if (a[child] < a[parent])//最小的孩子比parent的值小，就交換
{
Swap(&a[child], &a[parent]);
parent = child;//更新parent
child = parent * 2 + 1;//更新child，也假設(shè)最小的孩子是左孩子
}
else//最小的孩子比父親節(jié)點(diǎn)的值大，已經(jīng)不需要調(diào)整，是小堆了。
{
break;
}
}
}
?? 堆的數(shù)據(jù)的個(gè)數(shù)
直接返回_size的值。
// 堆的數(shù)據(jù)個(gè)數(shù)
int HeapSize(Heap* hp)
{
assert(hp);//hp不為空
return hp->_size;
}
?? 堆的判空
如果_size不為0，堆就不為空。
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
if (hp->_size == 0)//為空返回1
return 1;
else//不為空返回0
return 0;
}
?? 堆頂元素
堆頂元素在下標(biāo)為0的位置。
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
return hp->_a[0];
}
?? 堆的銷毀
堆的銷毀實(shí)際上主要要做的就是回收在堆上開的空間，將相應(yīng)的指針置為空，空間和元素大小置為0。
// 堆的銷毀
void HeapDestory(Heap* hp)
{
assert(hp);//hp不為空
assert(hp->_size > 0);//元素個(gè)數(shù)要大于0
free(hp->_a);//釋放空間
hp->_a = NULL;//將動(dòng)態(tài)數(shù)組的指針置為空
hp->_capacity = hp->_size = 0;//將空間和元素大小置為0
}
?? 堆排序
由于小堆和大堆的堆頂元素都是最小或者最大的，所以我們pop堆頂元素，然后再剩下的元素調(diào)整，就能得到一個(gè)有序的序列。
?? 版本1 創(chuàng)建堆，通過push、pop進(jìn)行操作 (異地操作)
那我們?cè)撊绾螌?shí)現(xiàn)這個(gè)堆排序呢？下面的代碼可以嗎為什么？
void Heapsort(HPDataType* a, int n)
{
Heap hp1;//假設(shè)我們建一個(gè)小堆
HeapInit(&hp1);
for (int i = 0; i < n; ++i)
{
HeapPush(&hp1, a[i]);//插入對(duì)應(yīng)元素
}
for (int i = 0; i < n; ++i)
{
a[i] = HeapTop(&hp1);//將最小的元素依次給數(shù)組
HeapPop(&hp1);//pop堆頂元素
}
}
效果演示：
這種方法是不太好的，因?yàn)橄葧呵也徽剷r(shí)間復(fù)雜度的問題，我們?yōu)榱巳ソo數(shù)組排一個(gè)序，而建了一個(gè)堆，這個(gè)空間開銷是沒必要的，其實(shí)我們可以對(duì)數(shù)組原地建堆。
?? 版本2 向上調(diào)整建堆（原地操作）
//堆排序,向上調(diào)整
void Heapsort2(HPDataType* a, int n)
{
assert(a);
for (int i = 1; i < n; i++)//我們向上調(diào)整，原地建一個(gè)小堆
{
AdjustUp(a,i);
}
for (int end = n - 1; end >= 0; --end)
{
Swap(&a[0], &a[end]);//將堆頂元素放到堆最后面去
AdjustDown(a, 0, end);//此時(shí)的end就代表我們的元素個(gè)數(shù)
}
}
原地建堆，如果你想排降序，就需要建一個(gè)小堆，因?yàn)樾《训亩秧斣厥亲钚〉?，我們?cè)夭僮?，就可以將最小的和最后一個(gè)元素交換，這樣沒有破壞原來的結(jié)構(gòu)，走一個(gè)向下調(diào)整就可以恢復(fù)堆結(jié)構(gòu)。
時(shí)間復(fù)雜度：NlogN,向上調(diào)整建堆：NlogN,向下調(diào)整調(diào)整一次logN（一共調(diào)整了N次），所以總體的時(shí)間復(fù)雜度也是O(N*logN)。
?? 版本3----向下調(diào)整建堆（原地操作）
但是這樣就結(jié)束了嗎，我們發(fā)現(xiàn)如果使用上面這種方法，既要寫一個(gè)向上調(diào)整，也要寫一個(gè)向下調(diào)整，我只是想排個(gè)序，需要這么復(fù)雜嗎，難道就不能直接向下調(diào)整建堆嗎？這樣我就不用寫兩個(gè)了呀，調(diào)整那塊肯定要用向下調(diào)整的，不然就破壞堆的結(jié)構(gòu)了。
下面我們來介紹向下調(diào)整建堆
代碼實(shí)現(xiàn)：
//堆排序,向下調(diào)整
void Heapsort3(HPDataType* a, int n)
{
assert(a);
for (int i = (n-1-1)/2; i >= 0; i--)//我們向上調(diào)整，原地建一個(gè)小堆
{
AdjustDown(a,i,n);
}
for (int end = n - 1; end >= 0; --end)
{
Swap(&a[0], &a[end]);//將堆頂元素放到堆最后面去
AdjustDown(a, 0, end);//此時(shí)的end就代表我們的元素個(gè)數(shù)
}
}
運(yùn)行結(jié)果：
?? 向下調(diào)整建堆的時(shí)間復(fù)雜度分析
整體這種堆排序的時(shí)間復(fù)雜度也是O（N*logN）,建堆的消耗是O（N）,但是每一次調(diào)整的消耗還是logN,調(diào)整了次，量級(jí)還是和第二種一樣，但是向下調(diào)整建堆只需要寫一個(gè)向下調(diào)整，且向下調(diào)整建堆比向上調(diào)整建堆要更快。
?? topK問題
topK問題指的是讓我們求第K大，第K小等問題，思考一下，在一個(gè)亂序的數(shù)組里面，如果我們想要這樣來做，我們常規(guī)的解決辦法是什么？排序?。?！這樣來做的時(shí)間復(fù)雜度是N*logN,我們只是求第K大或者第K小的數(shù)，有必要把這些數(shù)全部排一遍順序嗎，答案是不用，下面讓我們來學(xué)習(xí)一下使用堆這種數(shù)據(jù)結(jié)構(gòu)來解決經(jīng)典的topK問題。
?? topK問題的分析
下面我們畫圖來分析一下topk問題具體的解決之道。
?? topK問題的代碼實(shí)現(xiàn)
我們使用C語言的文件操作，造了100w個(gè)小于100w的數(shù)據(jù)（隨機(jī)值），然后我們求前5個(gè)大的數(shù)，我們這樣來驗(yàn)證，把文件里任意5個(gè)數(shù)改為大于100w的數(shù)，如果最后打印出來是我們改的5個(gè)數(shù)，證明我們的topk問題得到解決。
可以看到我們改了最后5個(gè)數(shù),修改之后把創(chuàng)建數(shù)據(jù)的程序注釋掉，防止它重新生成，我們的修改就沒意義了。
代碼實(shí)現(xiàn)：
void CreateNDate()
{
// 造數(shù)據(jù)
int n = 1000000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = rand() % 1000000;//造隨機(jī)數(shù)據(jù)，可以讓我們的測(cè)試程序得到更好的檢查
fprintf(fin, "%d\n", x);//將數(shù)據(jù)放入文件
}
fclose(fin);
}
void PrintTopK(int k)
{
const char* file = "data.txt";//定義文件
FILE* flout = fopen(file, "r");
if (flout == NULL)
{
perror("fopen failed");
exit(-1);
}
//開一個(gè)數(shù)組存放k個(gè)數(shù)據(jù)，開一個(gè)小堆
HPDataType* minheap = (HPDataType*)malloc(sizeof(HPDataType) * k);
if (minheap == NULL)
{
perror("malloc failed");
exit(-1);
}
for (int i = 0; i < k; i++)//將k個(gè)數(shù)放入數(shù)組中
{
fscanf(flout, "%d", &minheap[i]);
}
//向下調(diào)整建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minheap, i, k);
}
//遍歷，如果大于小堆堆頂?shù)臄?shù)據(jù)的話，就和它換，并向下調(diào)整
int x = 0;
while (fscanf(flout, "%d", &x) != EOF)
{
if (x > minheap[0])
{
Swap(&x, &minheap[0]);
AdjustDown(minheap, 0,k);
}
}
for (int i = 0; i < k; i++)//打印前k大的數(shù)
{
printf("%d ", minheap[i]);
}
fclose(flout);//關(guān)閉文件
}
int main()
{
CreateNDate();//造10w個(gè)數(shù)據(jù)
PrintTopK(5);
return 0;
}
運(yùn)行結(jié)果：
可以看到預(yù)期結(jié)果和我們修改的數(shù)是一致的，說明我們的代碼應(yīng)該沒啥問題。
?? top問題的時(shí)間復(fù)雜度和空間復(fù)雜度分析
?? 測(cè)試程序
下面我們來測(cè)試一下我們寫的上述方法的正確性如何。
?? 打印堆
我們可能需要把堆打印出來看結(jié)果。
//打印堆
void HeapPrint(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
for (int i = 0; i < hp->_size; i++)
{
printf("%d ", hp->_a[i]);
}
printf("\n");
}
?? 驗(yàn)證是否是一個(gè)堆
我們應(yīng)該如何驗(yàn)證我們的數(shù)據(jù)是否是一個(gè)小堆呢？其實(shí)很簡單，數(shù)組是順序存儲(chǔ)的，我們的數(shù)據(jù)一定是完全二叉樹，這個(gè)不用驗(yàn)證，關(guān)鍵是驗(yàn)證我們的數(shù)據(jù)是否都滿足小堆的定義，即所有的根節(jié)點(diǎn)的值都比它的左子樹的和右子樹的根節(jié)點(diǎn)的值要小，我們可以走一個(gè)前序遍歷來驗(yàn)證。
//驗(yàn)證是否是一個(gè)小堆
int is_Heap(HPDataType* a, int n,int root)
{
if (root >= n)
return 1;
int leftchild = root * 2 + 1;//左孩子的下標(biāo)
int rightchild = root * 2 + 2;//右孩子的下標(biāo)
if (leftchild < n && a[root] > a[leftchild])//左孩子存在且小于根，返回0，并打印相關(guān)信息
{
printf("%d\n位置不滿足小堆", root);
return 0;
}
if (rightchild < n && a[root] > a[rightchild])//右孩子存在且小于根，返回0，并打印相關(guān)信息
{
printf("%d\n位置不滿足小堆", root);
return 0;
}
return is_Heap(a, n, leftchild) && is_Heap(a, n, rightchild);//左樹和右樹都滿足小堆就返回1
}
?? 測(cè)試程序
void Test2()
{
Heap hp1;//建堆
HeapInit(&hp1);//初始化堆
//造10w個(gè)數(shù)據(jù)進(jìn)堆
int N = 100000;
srand(time(NULL));//通過時(shí)間來初始化隨機(jī)數(shù)種子
for (int i = 0; i < N; ++i)
{
HeapPush(&hp1, rand() % (10000000));//將數(shù)據(jù)存入堆里面
}
int i = is_Heap(hp1._a,N,0);//驗(yàn)證是否為堆
if (i)//打印提示信息
printf("是堆\n");
else
printf("不是堆\n");
printf("堆的元素個(gè)數(shù)為%d\n", HeapSize(&hp1));//驗(yàn)證元素個(gè)數(shù)方法是否正確
printf("堆頂元素為：%d\n", HeapTop(&hp1));//驗(yàn)證堆頂元素是否正確
HeapPop(&hp1);//驗(yàn)證pop函數(shù)是否正確
printf("堆的元素個(gè)數(shù)為%d\n", HeapSize(&hp1));
printf("堆頂元素為：%d\n", HeapTop(&hp1));
hp1._a[3] = -1;//破壞堆的結(jié)構(gòu)
i = is_Heap(hp1._a, N, 0);
if (i)
printf("是堆\n");
else
printf("不是堆\n");
HeapDestory(&hp1);
if (hp1._a == NULL)
printf("銷毀成功\n");
}
運(yùn)行結(jié)果：文章來源：http://www.zghlxwxcb.cn/news/detail-844821.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-844821.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)初階】之堆（C語言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
