在數(shù)據(jù)結(jié)構(gòu)中，二叉樹是非常好用的一種數(shù)據(jù)結(jié)構(gòu)，這節(jié)暫時(shí)按下不表。這節(jié)課主要介紹堆的建立與使用。

堆，是二叉樹中一種很特殊的結(jié)構(gòu)，首先，他必須是滿二叉樹，也就是除了最后一層以外，其他層都是滿的。

堆對(duì)于節(jié)點(diǎn)數(shù)據(jù)也有要求，其基本按照某種規(guī)律進(jìn)行排序。首先堆分為大堆和小堆。大堆上大小大小堆上小下大。有非常大的差距。并且在堆中每個(gè)節(jié)點(diǎn)也滿足完全二叉樹的父子節(jié)點(diǎn)規(guī)律，既child=parent*2+1 | 2,1和2取決于是子左節(jié)點(diǎn)還是右節(jié)點(diǎn)。

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

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;//child = father*2+1 | 2;

一個(gè)堆的基本結(jié)構(gòu)體如上圖所示，它應(yīng)該有一個(gè)特定類型的指針_a，一個(gè)代表堆目前數(shù)量的size，一個(gè)代表目前容量的_capacity。為什么選擇順序表作為建堆類型呢？首先是因?yàn)槎巡恍枰谥虚g插入數(shù)據(jù)，他是滿二叉樹；第二是因?yàn)槔脭?shù)組來建隊(duì)可以發(fā)現(xiàn)數(shù)組的下標(biāo)之間的關(guān)系，就是這個(gè)公式：child=parent*2+1 | 2，便于進(jìn)行計(jì)算。本文前半部分基本以小堆為準(zhǔn)。

堆的初始化

void HeapInit(Heap* php)
{assert(php);php->_a = NULL;php->_capacity = 0;php->_size = 0;
}//函數(shù)初始化Heap* HeapKCreat(int k)
{Heap* hp = (Heap*)malloc(sizeof(Heap));if (hp == NULL){perror("fail:hp creat");exit(1);}int* arr = (int*)malloc(sizeof(int) * k);hp->_a = arr;hp->_size = 0;hp->_capacity = 0;return hp;
}函數(shù)創(chuàng)建

堆的創(chuàng)建分為兩種方式，一種是在外面申請(qǐng)空間，然后再函數(shù)內(nèi)設(shè)置數(shù)據(jù)，一種是直接在函數(shù)內(nèi)部完成一切，總體而言還是簡單的把相關(guān)數(shù)據(jù)進(jìn)行簡單設(shè)置。

堆的銷毀

void HeapDestory(Heap* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_capacity = hp->_size = 0;
}

堆的銷毀也較為簡單，便是順序表的銷毀。其中有一個(gè)地方需要注意，便是需要先把數(shù)組給free掉。

堆的兩種整理方式

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

第一個(gè)函數(shù)是從下往上整理，先設(shè)置一個(gè)parent變量，這個(gè)變量便是孩子的父節(jié)點(diǎn)，因?yàn)?操作符的整除性，所以會(huì)自動(dòng)得到對(duì)應(yīng)節(jié)點(diǎn)。接著比較子節(jié)點(diǎn)大小與父節(jié)點(diǎn)大小的，若父節(jié)點(diǎn)大于子節(jié)點(diǎn)，那就父子對(duì)換，并讓子為父，在重新設(shè)置父節(jié)點(diǎn)。一直到父節(jié)點(diǎn)不再大于子節(jié)點(diǎn)或者子節(jié)點(diǎn)到了頂部。

void AdjustDowm(HPDataType* obj, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (obj[child + 1] < obj[child] && child + 1 < n){child++;}if (obj[parent] > obj[child]){Swap(&obj[child], &obj[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

另一種方案是從上往下整理，同樣的初始造個(gè)兒子操作。接著，判斷兒子不要超過數(shù)組數(shù)據(jù)大小范圍，這個(gè)設(shè)置出來的兒子是左兒子，接著判斷右兒子和左兒子的大小關(guān)系.若是右兒子要大一些的話，那就讓右兒子來和父節(jié)點(diǎn)較量較量。接著，若父節(jié)點(diǎn)大于子節(jié)點(diǎn)的話，那便換位置。一直到循環(huán)結(jié)束。

這兩種方法總體而言方法二會(huì)更好一點(diǎn)，方法二的時(shí)間復(fù)雜度為O(logN),方法一為O(N).具體計(jì)算方法可以上b站查一下。

堆的數(shù)據(jù)增加

void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->_capacity == hp->_size){int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;HPDataType* b = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));if (b == NULL){exit(1);}hp->_a = b;hp->_capacity = newcapacity;}hp->_a[hp->_size] = x;hp->_size++;AdjustUp(hp->_a, hp->_size - 1);
}

堆的push首先斷言一下，防止輸入的結(jié)構(gòu)體為空。接著，若此時(shí)容量等于當(dāng)前數(shù)據(jù)量，那么會(huì)進(jìn)入擴(kuò)容階段。此處建立一個(gè)一個(gè)newcapacity，利用三目操作符，如果此時(shí)容量大小為0，那么調(diào)整為4，若不是0，那么擴(kuò)容兩倍。接著realloc一個(gè)新的結(jié)構(gòu)體指針，其大小便是調(diào)整后的新容量。接著在判斷一下realloc是否成功，接著將realloc出來的指針給結(jié)構(gòu)體中的_a指針，然后吧容量變?yōu)樾碌娜萘?。接著就開始進(jìn)行賦值，把數(shù)據(jù)x放在數(shù)組的最后一個(gè)空地址，接著將size++。再然后向上調(diào)整或者向下調(diào)整都是可以的。這里便選擇了向上調(diào)整了。

堆的刪除

void HeapPop(Heap* hp)
{assert(hp);assert(hp->_size > 0);Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);hp->_size--;AdjustDowm(hp->_a, hp->_size, 0);}

堆的刪除首先要先確定不是空指針和堆里確實(shí)有數(shù)據(jù)。接著交換一下堆頂數(shù)據(jù)和堆底數(shù)據(jù)。將hp的size--，保證后續(xù)讀取不到要?jiǎng)h除的數(shù)據(jù)。接著將堆頂數(shù)據(jù)向下調(diào)整即可。

堆的部分簡單判斷與取數(shù)據(jù)

HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp->_size > 0);return hp->_a[0];
}//取堆頂數(shù)據(jù)int HeapSize(Heap* hp)
{assert(hp);return hp->_size;
}取堆大小int HeapEmpty(Heap* hp)
{assert(hp);return hp->_size == 0;
}判斷堆是否空了

堆的排序

void HeapSort(int* a, int n)
{//for (int i = 0; i < n; i++)//{//	AdjustUp(a, a[i]);//}空間要求較多，建議從下往上整，既下面方案int end = n - 1;while (end--)//{Swap(&a[0], &a[end]);AdjustDowm(a, n, 0);}
}

說是堆的排序，但其實(shí)針對(duì)于任何混亂的數(shù)組，將他們整理成有序的堆。堆的排序分為兩種方式，第一種方法是從上面的代碼，但是其堆空間的要求較多，因此較為推薦下面的方法。

TopK問題

我們建堆是為了什么呢？建堆一個(gè)很重要的意義便是找出最大的幾個(gè)數(shù)據(jù)或者最小的幾個(gè)數(shù)據(jù)。一個(gè)很大的數(shù)據(jù)本，要求前k個(gè)最大的數(shù)據(jù)，可以通過什么方法呢？一個(gè)相對(duì)好用的方法就是通過建容量為k的小堆，然后逐漸替換堆內(nèi)的數(shù)據(jù)來達(dá)成這個(gè)容量為k的小堆內(nèi)的數(shù)據(jù)便是原數(shù)據(jù)庫的前k個(gè)最大的數(shù)據(jù)。具體實(shí)現(xiàn)過程如下

創(chuàng)建數(shù)據(jù)庫

void CreateNDate()
{// 造數(shù)據(jù)int n = 100000;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;fprintf(fin, "%d\n", x);}fclose(fin);
}

首先我們先來利用time的偽隨機(jī)來創(chuàng)建一個(gè)數(shù)據(jù)庫，內(nèi)部包含10萬個(gè)隨機(jī)的數(shù)據(jù)，并將這些數(shù)據(jù)寫入名字為data的txt文件，這就是我們后面用來舉例的數(shù)據(jù)庫了。

topk數(shù)據(jù)庫

void PrintTopK(int k)
{int* arr = (int*)malloc(sizeof(int)*k);char* file = "data.txt";FILE* fin = fopen(file, "r");for (int i = 0; i < k; i++){fscanf(fin, "%d ",&arr[i]);}int a = 0;while (fscanf(fin, "%d ", &a)!=EOF) {if (a > arr[0]){arr[0] = a;AdjustDowm(arr,k,0);}}for (int i = 0; i < k; i++){printf("%d ", arr[i]);}}

首先，我們需要先創(chuàng)建出一個(gè)容量符合小堆的數(shù)組，因?yàn)槲疫@里的數(shù)據(jù)都是整型，因此便直接使用int類型了。接著打開data文件，首先將data中前10個(gè)數(shù)據(jù)寫入arr數(shù)組，接著設(shè)置一個(gè)普普通通的int類型數(shù)據(jù)a，接著進(jìn)入while循環(huán)，fscanf會(huì)返回讀到的數(shù)據(jù)數(shù)量，當(dāng)沒有數(shù)據(jù)的時(shí)候，則返回EOF，當(dāng)還有數(shù)據(jù)的時(shí)候，將數(shù)據(jù)寫入a中，判斷a和arr[0]的大小關(guān)系。若arr[0]小于a，則將a寫入數(shù)組中成為堆頂。接著向下調(diào)整剛剛寫入的數(shù)據(jù)。直到已經(jīng)將data文件中的數(shù)據(jù)全部讀了一遍，此時(shí)數(shù)組中包含的數(shù)據(jù)便是所有的最大數(shù)據(jù)。接著將這些數(shù)據(jù)打印出來，便得到了TopK個(gè)數(shù)據(jù)了。