目錄

1.堆的認(rèn)識

什么是堆

堆的性質(zhì)

2.堆的存儲

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

Heap.h中接口總覽

具體實(shí)現(xiàn)

堆結(jié)構(gòu)的定義

初始化堆

銷毀堆

堆的插入

堆的向上調(diào)整算法

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

堆的刪除

堆的向下調(diào)整算法

堆的刪除的實(shí)現(xiàn)?

使用數(shù)組初始化堆

獲取堆頂元素

獲取堆中的數(shù)據(jù)個數(shù)

判斷堆是否為空

打印堆中的元素

4.堆的應(yīng)用

堆排序

堆排序的思想

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

實(shí)現(xiàn)步驟

堆的創(chuàng)建

堆排序測試代碼

TOP-K問題

什么是top-k問題

解決top-k問題的思路

堆排序示例代碼

5.堆的實(shí)現(xiàn)代碼附錄

Heap.h

Heap.c

---

1.堆的認(rèn)識

什么是堆

想要弄清楚什么是堆，首先需要了解二叉樹的相關(guān)知識，推薦閱讀數(shù)據(jù)結(jié)構(gòu)——樹和二叉樹簡介。

堆分為大根堆和小根堆：

• 大根堆：如果一棵完全二叉樹中除了葉子結(jié)點(diǎn)的每個結(jié)點(diǎn)的值都大于其左右孩子，則這棵完全二叉樹就叫做大根堆。大根堆的對頂元素是這棵樹中的最大元素。

• 小根堆：如果一棵完全二叉樹中除了葉子結(jié)點(diǎn)的每個結(jié)點(diǎn)的值都小于其左右孩子，則這棵完全二叉樹就叫做小根堆。小根堆的堆頂元素是整棵樹的最小元素。

堆的性質(zhì)

1、堆總是一棵完全二叉樹

2、大根堆中每個結(jié)點(diǎn)的值總是不大于其父結(jié)點(diǎn)的值，小根堆中每個結(jié)點(diǎn)的值總是不小于其父結(jié)點(diǎn)的值。

2.堆的存儲

堆是完全二叉樹的特殊情況，完全二叉樹是二叉樹的特殊情況，二叉樹的存儲可以用順序結(jié)構(gòu)存儲和鏈?zhǔn)浇Y(jié)構(gòu)存儲。完全二叉樹的結(jié)點(diǎn)從上到下，從左到右是依次連續(xù)的，更適合用順序結(jié)構(gòu)存儲，因?yàn)椴粫锌臻g的浪費(fèi)，所以堆的存儲是用順序結(jié)構(gòu)存儲的，也就是使用數(shù)組存儲。

使用數(shù)組存儲堆的具體做法如下：

• 對每個結(jié)點(diǎn)從上到下，從左到右依次從0開始編號。
• 結(jié)點(diǎn)編的號對于數(shù)組的下標(biāo)。
• 數(shù)組下標(biāo)對應(yīng)的空間中保存結(jié)點(diǎn)的數(shù)據(jù)。

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

堆的實(shí)現(xiàn)，我們主要實(shí)現(xiàn)Heap.h和Heap.c文件，Heap.h中存放聲明，Heap.c中存放定義。

(文末附源碼！)

Heap.h中接口總覽

具體實(shí)現(xiàn)

堆結(jié)構(gòu)的定義

我們使用數(shù)組來存儲堆，并且采用動態(tài)的數(shù)組，所以堆結(jié)構(gòu)的定義如下：

• a指向底層的數(shù)組空間。
• size記錄有效數(shù)據(jù)的個數(shù)。
• capacity記錄空間的大小，當(dāng)空間不夠時自動擴(kuò)容。

初始化堆

當(dāng)我們定義堆結(jié)構(gòu)之后，在使用堆結(jié)構(gòu)之前，需要將堆進(jìn)行初始化：

• 首先需要判斷指向堆的指針是否為空，該指針不能為空。后面涉及該指針都需要判空，將不再贅述。
• a初始化為空指針。
• size和capacity都初始化為0。

銷毀堆

銷毀堆，就是釋放其結(jié)構(gòu)，釋放底層的數(shù)組空間，并將指向數(shù)組空間的指針置空，size和capacity都置為0即可。

堆的插入

我們采用數(shù)組存儲堆，想堆中插入數(shù)據(jù)其實(shí)就是向數(shù)組中插入數(shù)據(jù)，在數(shù)組的尾部插入的時間復(fù)雜度是O(1)，非常高效，所以堆的插入也采用尾插，但是，插入數(shù)據(jù)之后，堆結(jié)構(gòu)有可能被破壞。

如下圖：向堆中插入-1，此時插入的節(jié)點(diǎn)的值小于其父結(jié)點(diǎn)的值，不符合小根堆的特點(diǎn)，破壞了堆的結(jié)構(gòu)，所以需要進(jìn)行調(diào)整。我們采用堆的向上調(diào)整算法。

堆的向上調(diào)整算法

向上調(diào)整的前提：前面的數(shù)據(jù)是堆。

算法步驟如下：

• 1.將當(dāng)前結(jié)點(diǎn)的值和父結(jié)點(diǎn)的值比較，判斷是否符合當(dāng)前堆的性質(zhì)。
• 2.如果滿足則無需調(diào)整，不滿足則和父結(jié)點(diǎn)的值交換。
• 3.交換完之后重復(fù)1過程。

向上調(diào)整代碼如下：?

向上調(diào)整算法時間復(fù)雜度分析：堆的向上調(diào)整算法在最優(yōu)情況下不需要調(diào)整，在最壞情況下需要調(diào)整樹的高度-1次。所以時間復(fù)雜度是O(logN)。

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

在堆中插入數(shù)據(jù)可以分如下幾步實(shí)現(xiàn)：

• 1.首先判斷是否需要擴(kuò)容。
• 2.在數(shù)組空間的末尾插入數(shù)據(jù)，記得將size++。
• 3.然后進(jìn)行向上調(diào)整。

堆的刪除

刪除堆的元素的時候，刪除的是堆頂?shù)脑?#xff0c;這是堆的特點(diǎn)。堆的存儲采用的是數(shù)組空間，刪除堆中的堆頂元素刪除的就是數(shù)組空間中的第一個元素，數(shù)組進(jìn)行頭刪的時間復(fù)雜度是O(N)，效率不高，于是，我們采用替換法刪除，首先將堆數(shù)組的第一個元素和最后一個元素刪除，然后刪除最后一個元素即可。

但是，這里有一個和堆的插入相同的問題，刪除元素之后，堆的結(jié)構(gòu)可能會被破壞。這就需要使用向下調(diào)整算法來調(diào)整堆的結(jié)構(gòu)了。

堆的向下調(diào)整算法

向下調(diào)整的前提：左右子樹是堆。

算法步驟如下：

• 1.計(jì)算出左孩子的下標(biāo)。
• 2.如果是小堆，找出兩個孩子中小的那個；如果是大堆，找出兩個孩子中大的那個。
• 3.判斷父結(jié)點(diǎn)和選擇的孩子結(jié)點(diǎn)是否滿足當(dāng)前堆的性質(zhì)。
• 4.如果滿足則不需要調(diào)整了，標(biāo)識當(dāng)前二叉樹符合堆的性質(zhì)。
• 5.不滿足則交換，并且更新父結(jié)點(diǎn)和孩子結(jié)點(diǎn)的值，再次調(diào)整，重復(fù)2步驟。

向下調(diào)整代碼如下：?

向下調(diào)整算法時間復(fù)雜度分析：堆的向下調(diào)整算法在最優(yōu)情況下不需要調(diào)整，在最壞情況下需要調(diào)整樹的高度-1次。所以時間復(fù)雜度是O(logN)。?

堆的刪除的實(shí)現(xiàn)?

刪除堆頂元素可以分如下幾步進(jìn)行：

• 1.將第一個元素和最后一個元素交換。
• 2.將size--，表示有效數(shù)據(jù)減1。
• 3.進(jìn)行向下調(diào)整，保持堆的結(jié)構(gòu)。

使用數(shù)組初始化堆

在使用堆的時候，我們需要使用數(shù)據(jù)來初始化堆，也就是建堆。建堆可以使用向上調(diào)整建堆，也可以使用向下調(diào)整建堆，這里我們使用向上調(diào)整建堆。

向上調(diào)整建堆的步驟：

• 1.動態(tài)申請一塊堆空間，并判斷申請是否成功。
• 2.size 和 capacity都置為待初始化數(shù)組的大小。
• 3.把數(shù)據(jù)從待拷貝數(shù)組拷貝到堆數(shù)組中。
• 4.從第二個元素開始，逐元素進(jìn)行向上調(diào)整建堆。

向上調(diào)整建堆代碼如下：

獲取堆頂元素

堆頂元素就是底層數(shù)組空間中的第一個元素，直接返回下標(biāo)為0的元素即可。

獲取堆中的數(shù)據(jù)個數(shù)

size就是用來記錄有效元素個數(shù)的，直接返回size即可。

判斷堆是否為空

當(dāng)size == 0的時候，說明堆中沒有元素，直接判斷size是否等于0即可。

打印堆中的元素

遍歷打印即可。

4.堆的應(yīng)用

堆的應(yīng)用主要有堆排序和解決TOP-K問題。

堆排序

堆排序的思想

參考堆刪除的思想來排序，刪除堆頂元素的時候，我們使用的是替換法刪除，也就是將堆頂元素放到當(dāng)前數(shù)組末尾，每次選擇的是堆中當(dāng)前的最大or最小元素。相當(dāng)于每次都能選出一個值，從后往前填入如數(shù)組。

• 如果是大堆，每次選出的數(shù)據(jù)就是當(dāng)前堆中最大的元素，從數(shù)組后面往前填入數(shù)組，排出來的數(shù)據(jù)是升序的。
• 如果是小堆，每次選出的數(shù)據(jù)就是當(dāng)前堆中最小的元素，從數(shù)組后面往前填入數(shù)組，排出來的數(shù)據(jù)是降序的。

所以，如果我們想排升序，建堆的時候，應(yīng)該建立大堆；如果我們想排降序，建堆的時候，應(yīng)該建立小堆。

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

實(shí)現(xiàn)步驟

• 先建堆。排升序，建立大堆；排降序，建立小堆。
• 對堆結(jié)構(gòu)進(jìn)行向下調(diào)整，每次選出一個數(shù)放在正確的位置。

堆的創(chuàng)建

建堆有兩種方法，一種是向上調(diào)整建堆，一種是向下調(diào)整建堆。

向上調(diào)整建堆：向上調(diào)整的前提是前面的數(shù)據(jù)是堆，所以，數(shù)據(jù)應(yīng)該從上往下，從做往右依次進(jìn)行向上調(diào)整。一個數(shù)據(jù)通過向上調(diào)整建堆最多調(diào)整樹的高度-1次，也就是logN，一共N個數(shù)據(jù)，所以向上調(diào)整建堆的時間復(fù)雜度是O(N*logN)。

向下調(diào)整建堆：向下調(diào)整的前提是左右子樹是堆，也就是后面的數(shù)據(jù)是堆，因?yàn)?#xff0c;葉子結(jié)點(diǎn)沒有孩子，所以應(yīng)該從倒數(shù)第一個非葉子結(jié)點(diǎn)開始進(jìn)行向下調(diào)整。

向下調(diào)整建堆的時間復(fù)雜度為O(N)，要優(yōu)于向上調(diào)整建堆。?

堆排序測試代碼

#include <iostream>
using namespace std;typedef int HPDataType;
typedef struct Heap
{HPDataType* a;  // 指向底層的數(shù)組空間 int size;       // 存儲的有效數(shù)據(jù)個數(shù) int capacity;   // 數(shù)組空間的容量大小 
}HP;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])    // 此處比較符號控制大小堆的創(chuàng)建 {Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 找出小的那個孩子if (child + 1 < n && a[child + 1] < a[child])// 此處比較符號控制大小堆的創(chuàng)建 {++child;}if (a[child] < a[parent])                    // 此處比較符號控制大小堆的創(chuàng)建 {Swap(&a[child], &a[parent]);// 繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向上調(diào)整建堆 排升序，建大堆  排降序，建小堆 // O(N*logN)/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/// 向下調(diào)整建堆// O(N)for (int i = (n-1-1)/2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int a[] = { 2,5,3,7,4,8,6 };HeapSort(a, sizeof(a) / sizeof(int));int i = 0;while(i < 7){cout << a[i] << ' ';i++;} return 0;
}

堆排序時間復(fù)雜度分析：向下調(diào)整選出一個正確的數(shù)的時間復(fù)雜度是O(logN)，一共有N個數(shù)，所以時間復(fù)雜度是O(N*log(N))。?

TOP-K問題

什么是top-k問題

top-k問題就是求數(shù)據(jù)集合中的前k個最大元素or最小元素。（一般數(shù)據(jù)量都比較大）比如：游戲中的前10名玩家……等等大規(guī)模的數(shù)據(jù)中找最小的or最大的k個元素的問題都是top-k問題。

解決top-k問題的思路

解決top-k問題最直接的方法就是排序，但是當(dāng)數(shù)據(jù)量非常大的時候，無法全部加載到內(nèi)存中的時候，就需要使用堆來解決。具體思路如下：

• 1.用數(shù)據(jù)集合中的前k個來建堆。求前k個最大，建小堆；求前k個最小，建大堆。
• 2.用剩余的n-k個元素依次與堆頂元素比較。如果建的是大堆，當(dāng)數(shù)據(jù)比堆頂元素小的時候替換堆頂元素；如果建的是小堆，當(dāng)數(shù)據(jù)比堆頂元素大的時候替換堆頂元素。

將剩余的n-k個元素比較完之后，堆中剩余的就是前k個最小or最大的元素。

堆排序示例代碼

#include <stdlib.h>
#include <time.h>void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k個元素建堆FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 前k個數(shù)建小堆for (int i = (k-2)/2; i >=0 ; --i){AdjustDown(minheap, k, i);}// 2. 將剩余n-k個元素依次與堆頂元素交換，不滿則則替換int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){// 替換你進(jìn)堆minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);fclose(fout);
}void CreateNDate()
{// 造數(shù)據(jù)int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{CreateNDate();PrintTopK("data.txt", 5);return 0;
}

5.堆的實(shí)現(xiàn)代碼附錄

Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;  // 指向底層的數(shù)組空間 int size;       // 存儲的有效數(shù)據(jù)個數(shù) int capacity;   // 數(shù)組空間的容量大小 
}HP;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 堆的向上調(diào)整 
void AdjustUp(HPDataType* a, int child);// 堆的向下調(diào)整 
void AdjustDown(HPDataType* a, int n, int parent);// 交換兩個元素 
void Swap(HPDataType* p1, HPDataType* p2);// 打印堆中的元素 
void HeapPrint(HP* php);// 初始化堆 
void HeapInit(HP* php);// 使用數(shù)組元素初始化堆 
void HeapInitArray(HP* php, int* a, int n);// 銷毀堆 
void HeapDestroy(HP* php);// 堆的插入 
void HeapPush(HP* php, HPDataType x);// 堆的刪除 
void HeapPop(HP* php);// 取堆頂元素 
HPDataType HeapTop(HP* php);// 堆的判空 
bool HeapEmpty(HP* php);// 獲取堆的數(shù)據(jù)個數(shù)
int HeapSize(HP* php); 

Heap.c

#include <Heap.h>void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;         // 計(jì)算父節(jié)點(diǎn) while (child > 0){if (a[child] > a[parent])         // 不符合堆的性質(zhì)，需要向上調(diào)整 {Swap(&a[child], &a[parent]);  // 交換雙親和孩子結(jié)點(diǎn)的值 // 孩子和雙親結(jié)點(diǎn)向上移動 child = parent;            parent = (parent - 1) / 2;}else                              // 符合堆的性質(zhì) {break;}}
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;  // 計(jì)算出左孩子結(jié)點(diǎn)的下標(biāo) while (child < n){// 找出小的那個孩子if (child + 1 < n && a[child + 1] < a[child]) // 如果右孩子小于左孩子{ ++child;                                  // 選擇右孩子 }if (a[child] < a[parent])  // 不滿足小堆的性質(zhì)，向下調(diào)整 {Swap(&a[child], &a[parent]);// 繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else                       // 滿足小堆的性質(zhì)，直接退出 {break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);// 判斷是否需要擴(kuò)容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;    // 二倍擴(kuò)容 HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity); // 申請空間 if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;                // 讓堆數(shù)組指針指向新空間 php->capacity = newCapacity; // 更新容量大小 }php->a[php->size] = x;           // 在尾部插入數(shù)據(jù) php->size++;                     // 有效數(shù)據(jù)++ AdjustUp(php->a, php->size - 1); // 向上調(diào)整，保持堆結(jié)構(gòu)的特性 
}void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]); // 交換首尾元素 --php->size;                              // --sizeAdjustDown(php->a, php->size, 0);         // 向下調(diào)整 
}void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);php->a = (HPDataType*)malloc(sizeof(HPDataType)*n); // 動態(tài)申請數(shù)組空間 if (php->a == NULL)                                 // 判斷空間的申請是否成功 {perror("malloc fail");exit(-1);}// size 和 capacity都置為待初始化數(shù)組的大小 php->size = n;php->capacity = n;// 把數(shù)據(jù)從待拷貝數(shù)組拷貝到堆數(shù)組中。 memcpy(php->a, a, sizeof(HPDataType) * n);// 向上調(diào)整建堆for (int i = 1; i < n; i++){AdjustUp(php->a, i);}
}HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0]; // 堆頂元素就是底層數(shù)組空間中的第一個元素 
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}// 獲取堆的數(shù)據(jù)個數(shù)
int HeapSize(HP* php);
{assert(php);return php->size;	
}void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}