前言

🚩前面了解了樹（-> 傳送門 <-）的概念后，本章帶大家來實(shí)現(xiàn)一個跟樹有關(guān)的數(shù)據(jù)結(jié)構(gòu)——堆（本章有對堆排序和topk問題的講解）。
🚩普通的二叉樹是不適合用數(shù)組來存儲的，因?yàn)榭赡軙嬖诖罅康目臻g浪費(fèi)。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。現(xiàn)實(shí)中我們通常把 堆 (一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
如下圖：

🚩所以，我們在實(shí)現(xiàn) 堆 的時(shí)候可以將它看作為一棵二叉樹來思考，這是它的 邏輯結(jié)構(gòu) 。但其 物理結(jié)構(gòu) 是一個實(shí)實(shí)在在的 順序數(shù)組 (在內(nèi)存當(dāng)中存儲的形式)。
🚩那么接下來就開始實(shí)現(xiàn)一個屬于自己的堆吧！

---

堆的概念及結(jié)構(gòu)

• 本章是以大堆為例，只要會了大堆，小堆也是不在話下。

• 堆是把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并且它的任意元素 Ki(i = 0, 1, 2, 3, …, n - 1) 都滿足 Ki <= K(i * 2 + 1) 且 Ki <= (i * 2 + 2) （ 或者 Ki >= K(i * 2 + 1) 且 Ki >= K(i * 2 + 2) ），這樣的堆我們稱之為 小堆（ 或者 大堆 ）。我們還可以將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
  堆的性質(zhì)：

  1. 堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
  2. 堆總是一棵完全二叉樹。

• 有了對堆的概念和性質(zhì)的理解，相信大家對堆的元素是如何在數(shù)組中存儲的（物理結(jié)構(gòu)）明白了許多，就是依照上面大堆小堆的概念來維持存儲關(guān)系的。

圖示：

• 觀察上圖可知，第一張圖是一個大堆的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，其每個結(jié)點(diǎn)的左右子結(jié)點(diǎn)都比這個結(jié)點(diǎn)要小或者等于；第二張圖是一個小堆的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，其每個結(jié)點(diǎn)的左右子結(jié)點(diǎn)都比這個結(jié)點(diǎn)要大或者等于。所以，一個堆，他只能是小堆或者大堆，不具有這兩個堆的性質(zhì)的，都不屬于堆，下面我們來判斷一下那些是堆那些不是堆：

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,80,70,65,100  // 這是一個小堆 
F. 50,100,70,65,60,32  // 這不是堆

其實(shí)如果想要更好的判斷，只需要將其邏輯結(jié)構(gòu)畫出來，就一目了然了。

了解了堆的概念和結(jié)構(gòu)后，接下來就是實(shí)現(xiàn)啦！！！

---

堆初始化

• 首先我們需要三個文件：heap.h，heap.c，test.c。heap.h用來存放所需頭文件，堆的結(jié)構(gòu)體和相關(guān)函數(shù)聲明。heap.c用來實(shí)現(xiàn)相關(guān)函數(shù)接口，test.c用來測試。

下面是所需頭文件：

#include <stdio.h>
// assert斷言所需
#include <assert.h>
// 動態(tài)內(nèi)存開辟函數(shù)所需
#include <stdlib.h>
// bool類型所需
#include <stdbool.h>
// 拷貝函數(shù)所需
#include <string.h>

• 我們知道，堆的底層存儲結(jié)構(gòu)是一個順序的數(shù)組，因此這里需要跟前面我們實(shí)現(xiàn)的順序表一樣用動態(tài)內(nèi)存空間。使用動態(tài)空間，就需要一個變量來統(tǒng)計(jì)容量，當(dāng)然，為了后面一些函數(shù)功能的需求，還需要一個變量來統(tǒng)計(jì)堆的數(shù)據(jù)個數(shù)。因此，一個堆的結(jié)構(gòu)定義如下：

// 堆的元素的數(shù)據(jù)類型
typedef int HPDataType;
typedef struct Heap
{// 指向存儲數(shù)據(jù)的連續(xù)的空間（數(shù)組）HPDataType* a;// 統(tǒng)計(jì)當(dāng)前堆中數(shù)據(jù)的個數(shù)int size;// 統(tǒng)計(jì)當(dāng)前空間的容量int capacity;
}Heap;

• 一個堆所需的函數(shù)接口聲明如下：

// 以大堆為例
// 堆初始化
void HeapInit(Heap* php);
// 數(shù)組創(chuàng)建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n);// 插入數(shù)據(jù)
void HeapPush(Heap* php, HPDataType x);
// 刪除數(shù)據(jù)
void HeapPop(Heap* php);// 獲取堆頂數(shù)據(jù)
HPDataType HeapTop(Heap* php);// 獲取堆數(shù)據(jù)個數(shù)
int HeapSize(Heap* php);// 堆判空
bool HeapEmpty(Heap* php);// 堆的銷毀
void HeapDestroy(Heap* php);// 交換
void swap(HPDataType* a, HPDataType* b);
// 向上調(diào)整
void adjustup(HPDataType* a, int child);
// 向下調(diào)整
void adjustdown(HPDataType* a, int size, int parent);// 堆排序
void HeapSort(HPDataType* a, int n);
// topk問題
void PrintTopK(HPDataType* a, int n, int k);

• 有了以上的鋪墊，堆的初始化就是將堆的結(jié)構(gòu)里的指針置為空，統(tǒng)計(jì)數(shù)據(jù)個數(shù)和統(tǒng)計(jì)空間容量的變量置為0即可。(當(dāng)然也可以初始化的時(shí)候就開個初始空間)

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 堆初始化
void HeapInit(Heap* php)
{// 防止傳遞一個NULL上來，傳NULL的話php就是NULL，后面的操作就不能進(jìn)行了assert(php);php->a = NULL;php->capacity = php->size = 0;
}

---

堆的判空

• 有了統(tǒng)計(jì)堆的數(shù)據(jù)個數(shù)的變量size，判空就簡單多了。只需要判斷一下size是否為0即可，如果size為0，說明為空，返回true，如果size不為0，說明堆中有數(shù)據(jù)，返回false。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 堆判空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

---

堆的銷毀

• 堆的銷毀也很簡單，將堆空間釋放即可。當(dāng)然size跟統(tǒng)計(jì)容量的capacity也置為0。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 堆的銷毀
void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->capacity = php->size = 0;
}

---

插入數(shù)據(jù)

• 首先，插入數(shù)據(jù)要看看容量夠不夠，如果不夠，就需要擴(kuò)容。

• 插入數(shù)據(jù)就是在數(shù)組的最后一個位置插入，由于size是數(shù)據(jù)的個數(shù)也就是數(shù)組的長度，所以size就是指向堆的最后一個數(shù)據(jù)的下一個位置，因此我們只需要在size位置插入即可。當(dāng)然，插入過后，多了一個數(shù)據(jù)，因此size要自加1。

• 當(dāng)我們插入數(shù)據(jù)之后，現(xiàn)在堆的結(jié)構(gòu)很可能就不是一個堆（以大堆為例）了，因此，這里需要對插入進(jìn)來的那個數(shù)據(jù)執(zhí)行一個向上調(diào)整的算法，圖示：

• 對于向上調(diào)整算法，我們需要找到這個結(jié)點(diǎn)（假設(shè)下標(biāo)為child）的父親結(jié)點(diǎn)（假設(shè)下標(biāo)為parent），具體操作為：parent = (child - 1) / 2 ，找到父結(jié)點(diǎn)后，就與他進(jìn)行比較，由于我們以大堆為例，所以如果child位置上的數(shù)據(jù)大于parent位置上的數(shù)據(jù)，就需要將這兩個數(shù)據(jù)交換一下，然后循環(huán)往復(fù)，繼續(xù)尋找父結(jié)點(diǎn)進(jìn)行比較，直到到達(dá)應(yīng)該處在的位置為止（直到是個堆為止）。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 插入數(shù)據(jù)
void HeapPush(Heap* php, HPDataType x)
{assert(php);// 如果容量滿了就擴(kuò)容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}// 在size位置插入數(shù)據(jù)，然后size自加1php->a[php->size++] = x;// 對插入的那個數(shù)據(jù)執(zhí)行向上調(diào)整算法，重整堆// php->size - 1是插入的那個數(shù)據(jù)的下標(biāo)adjustup(php->a, php->size - 1);
}

向上調(diào)整算法：

// 向上調(diào)整
void adjustup(HPDataType* a, int child)
{// 找父結(jié)點(diǎn)int parent = (child - 1) / 2;while (child > 0){// 如果child位置的數(shù)據(jù)大小大于parent位置的數(shù)據(jù)大小就交換if (a[child] > a[parent]){// 交換swap(&a[child], &a[parent]);// 交換過后，child依舊指向開始指向的那個數(shù)據(jù)child = parent;// 繼續(xù)找父結(jié)點(diǎn)parent = (child - 1) / 2;}else break; // 如果小于等于了，說明此時(shí)的堆是個真正的堆了，直接跳出循環(huán)}
}

這里有個swap函數(shù)，其實(shí)現(xiàn)為：

// 交換
// 注意是傳遞地址交換，因?yàn)樾螀⒌母淖儾桓淖儗?shí)參
void swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}

---

刪除數(shù)據(jù)

• 刪除數(shù)據(jù)其實(shí)是刪除堆頂?shù)臄?shù)據(jù)，由于堆是由一個數(shù)組來存放數(shù)據(jù)的，那么我們該如何刪除堆頂（數(shù)組的第一個元素?cái)?shù)據(jù)）的數(shù)據(jù)呢？

• 這里我們將堆頂數(shù)據(jù)和數(shù)組的最后一個數(shù)據(jù)交換一下，然后size減一，就實(shí)現(xiàn)了刪除。

• 當(dāng)然，刪除過后，此時(shí)的堆已經(jīng)不再是堆了，所以我們需要對新的堆頂數(shù)據(jù)執(zhí)行一下向下調(diào)整算法，圖示：

• 對于向下調(diào)整算法，我們先要找到該結(jié)點(diǎn)（假設(shè)下標(biāo)為parent）的孩子結(jié)點(diǎn)，而孩子結(jié)點(diǎn)又分為左孩子結(jié)點(diǎn)（下標(biāo)為parent * 2 + 1）和右孩子結(jié)點(diǎn)（下標(biāo)為parent * 2 + 2），所以我們需要找出兩個孩子結(jié)點(diǎn)當(dāng)中較大的那個，如果該節(jié)點(diǎn)的數(shù)據(jù)比較大的那個孩子結(jié)點(diǎn)的數(shù)據(jù)要小，那就進(jìn)行交換，然后循環(huán)往復(fù)繼續(xù)向下尋找孩子結(jié)點(diǎn)重整堆。

• 整個操作，我們可以先比較兩個孩子的大小找出大的那個，然后在與大的這個孩子結(jié)點(diǎn)進(jìn)行比較，如果父結(jié)點(diǎn)比他小（以大堆為例），說明這個孩子結(jié)點(diǎn)該上位了。然后繼續(xù)向下執(zhí)行這個操作。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 刪除數(shù)據(jù)，刪除堆頂?shù)臄?shù)據(jù)
void HeapPop(Heap* php)
{// 判斷php的合法性并且要保證堆不為空，空就不能刪了assert(php && !HeapEmpty(php));// 將堆的第一個數(shù)據(jù)與堆的最后一個數(shù)據(jù)交換swap(&php->a[0], &php->a[php->size - 1]);// size減一表示刪除最后一個數(shù)據(jù)php->size--;// 對新的堆頂執(zhí)行向下調(diào)整算法adjustdown(php->a, php->size, 0);
}

向下調(diào)整算法：

// 向下調(diào)整
void adjustdown(HPDataType* a, int size, int parent)
{// 先假設(shè)大的那個孩子結(jié)點(diǎn)為左孩子結(jié)點(diǎn)int child = parent * 2 + 1;while (child < size)  // 如果child小于此時(shí)數(shù)組的長度就繼續(xù){// 第一個判斷是防止沒有右孩子結(jié)點(diǎn)的情況// 第二個判斷是如果右孩子存在并且右孩子結(jié)點(diǎn)的數(shù)據(jù)大于左孩子結(jié)點(diǎn)的數(shù)據(jù)，就child加一指向右孩子結(jié)點(diǎn)if (child + 1 < size && a[child + 1] > a[child]) child++;// 如果父節(jié)點(diǎn)數(shù)據(jù)小于child結(jié)點(diǎn)數(shù)據(jù)，就交換重整堆if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else break;  // 如果父節(jié)點(diǎn)數(shù)據(jù)大于child結(jié)點(diǎn)數(shù)據(jù)，說明堆已經(jīng)調(diào)整完畢，直接跳出循環(huán)不在調(diào)整}
}

---

堆的數(shù)據(jù)個數(shù)

• 由于我們定義了一個變量來統(tǒng)計(jì)堆的數(shù)據(jù)個數(shù)，所以在這里只需要返回那個變量的值即可。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 獲取堆數(shù)據(jù)個數(shù)
int HeapSize(Heap* php)
{assert(php);return php->size;
}

---

獲取堆頂數(shù)據(jù)

• 獲取堆頂數(shù)據(jù)就是數(shù)組的第一個元素。

• 如果此時(shí)堆為空，就不能獲取了。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 獲取堆頂數(shù)據(jù)
HPDataType HeapTop(Heap* php)
{assert(php && !HeapEmpty(php));return php->a[0];
}

---

用數(shù)組創(chuàng)建堆

• 用數(shù)組創(chuàng)建堆就是將一個數(shù)組里面的所有元素拷貝到堆的數(shù)組里，然后進(jìn)行建堆。

• 我們首先開辟一個堆空間（就是一段連續(xù)的數(shù)組），長度與給的數(shù)組的長度相同，然后將給的數(shù)組里的元素拷貝過來，最后將堆里面的數(shù)據(jù)進(jìn)行建堆。

• 如何建堆？我們從最后一個結(jié)點(diǎn)的父節(jié)點(diǎn)開始，依次執(zhí)行向下調(diào)整算法，直到根節(jié)點(diǎn)執(zhí)行完全后，便建成了堆。當(dāng)然我們也可以從第二個結(jié)點(diǎn)開始，依次執(zhí)行向上調(diào)整算法，直到最后一個結(jié)點(diǎn)執(zhí)行完后便建成了堆，不過這樣的時(shí)間復(fù)雜度為O(n * logn)，而前面的向下調(diào)整算法的方式的時(shí)間復(fù)雜度為O(n)，所以這里我們采用向下調(diào)整算法的方式來建堆。至于這兩個調(diào)整算法的時(shí)間復(fù)雜度是如何計(jì)算出來的，這里就不做討論，它的本質(zhì)其實(shí)是有關(guān)數(shù)列求和的計(jì)算。

向下調(diào)整算法方式建堆圖示：

• 有了上面的思路，接下來就是代碼實(shí)現(xiàn)了。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 數(shù)組創(chuàng)建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n)
{// php不能為NULL，a不能為NULLassert(php && a);// 開辟可存放n個數(shù)據(jù)的堆空間php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");exit(-1);}// 拷貝數(shù)據(jù)memcpy(php->a, a, sizeof(HPDataType) * n);php->size = php->capacity = n;// 從最后一個結(jié)點(diǎn)的父節(jié)點(diǎn)開始依次執(zhí)行向下調(diào)整算法，直到根結(jié)點(diǎn)執(zhí)行完后結(jié)束// 這里i為什么初始化 (n - 2) / 2 呢？ 其實(shí)就是最后一個結(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)// 前面說了，尋找父節(jié)點(diǎn)的下標(biāo)是 (child - 1) / 2// 這里是尋找最后一個結(jié)點(diǎn)的父結(jié)點(diǎn)，而最后一個結(jié)點(diǎn)的下標(biāo)是 (n - 1)（n是數(shù)組長度）// 所以它的父節(jié)點(diǎn)就是 (n - 1 - 1) / 2 , 也就是(n - 2) / 2for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(php->a, n, i);
}

---

對數(shù)組堆排序

• 有了建堆的認(rèn)識，堆排序也不難，只不過需要注意幾個細(xì)節(jié)。

• 對數(shù)組排序，首先就是要對這個數(shù)組建堆，如果是要將數(shù)組升序，就建為大堆，如果是要將數(shù)組降序，就建為小堆，為什么呢？這里以升序?yàn)槔M(jìn)行講解，弄懂了升序，降序也只是大于小于號的問題了。

• 當(dāng)數(shù)組建成大堆形式后（同樣的，使用向下調(diào)整算法建堆），堆頂元素是最大的，此時(shí)我們可以將堆頂元素與最后一個元素進(jìn)行交換，這樣最大的元素就到了數(shù)組的末尾了。然后我們對這個處在數(shù)組最后一個位置的最大元素視而不見，將交換過去的堆頂元素執(zhí)行向下調(diào)整算法，這時(shí)，第二大的元素就到了堆頂，然后此時(shí)的堆頂元素繼續(xù)與最后一個元素進(jìn)行交換 （注意第一個交換過去的最大的元素已經(jīng)不在范圍內(nèi)了，也就是說每將一個當(dāng)前最大的數(shù)交換過去后，可視作size減一一次） ，然后再將交換過去的堆頂元素執(zhí)行向下調(diào)整算法…這樣循環(huán)往復(fù)，最終該數(shù)組就變成了升序。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// 堆排序
void HeapSort(HPDataType* a, int n)
{assert(a);// 向下調(diào)整, 這里是建大堆for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(a, n, i);// 排序（建的大堆就是升序）int k = n - 1;while (k > 0){swap(&a[0], &a[k]);adjustdown(a, k, 0);k--;}
}

---

有關(guān)topk問題

• 如何在百萬個成績數(shù)據(jù)里面找出前十個最好的？這就是典型的topk問題?？梢钥吹?#xff0c;它需要處理的數(shù)據(jù)非常多（當(dāng)然也有的很少，不過面試一般就是問多的情況，讓你找出前k個最那啥的），因此這里需要用到堆來解決。

• 為什么堆可以解決呢？堆的堆頂要么是整個堆里最大的元素，要么是整個堆里最小的元素。根據(jù)這一性質(zhì)，假如求很多數(shù)據(jù)中前k個最小的數(shù)據(jù)，我們可以先開辟一個堆空間，該堆空間可以存放k個數(shù)據(jù)，然后我們將很多數(shù)據(jù)中的前k個數(shù)據(jù)拷貝進(jìn)堆里，并將其建成大堆，此時(shí)堆的堆頂元素就是堆里所有元素最大的那一個，接著，我們從很多數(shù)據(jù)的第k個數(shù)開始，遍歷這些數(shù)據(jù)，如果該數(shù)據(jù)小于此時(shí)堆頂?shù)臄?shù)據(jù)，就將堆頂數(shù)據(jù)更新為這個小的數(shù)據(jù)，然后對其執(zhí)行向下調(diào)整算法，執(zhí)行完過后，堆頂還是堆中最大的那個元素，就這樣判斷并操作，直到遍歷結(jié)束，堆中就是那前k個最小的數(shù)啦。最后將這些數(shù)打印即可。（找前k個最小的數(shù)就是建大堆，反之，建小堆，這里就不作討論了）

• 原理（以求前k個最小的數(shù)為例）：每次比堆頂小的元素入堆并調(diào)整后，之前堆中最大的元素被拋棄，新的最大的元素上位了，這樣循環(huán)往復(fù)下去，每次操作除大的進(jìn)小的，當(dāng)然最后堆中就是前k個最小的數(shù)啦。

相關(guān)函數(shù)接口功能的實(shí)現(xiàn)：

// topk問題
void PrintTopK(HPDataType* a, int n, int k)
{assert(a);// 開辟能夠存放k個數(shù)據(jù)的堆空間HPDataType* topk = (HPDataType*)malloc(sizeof(HPDataType) * k);if (topk == NULL){perror("malloc fail");exit(-1);}// 拷貝前k個數(shù)據(jù)進(jìn)堆memcpy(topk, a, sizeof(HPDataType) * k);// 找前k個最小的，建大堆for (int i = (k - 2) / 2; i >= 0; i--) adjustdown(topk, k, i);// 對topk堆進(jìn)行 除大的進(jìn)小的 操作for (int i = k; i < n; i++){if (a[i] < topk[0]){topk[0] = a[i];// 每次進(jìn)來一個較小的元素都要執(zhí)行一遍向下調(diào)整算法來調(diào)整堆adjustdown(topk, k, 0);}}// 打印  topkfor (int i = 0; i < k; i++) printf("%d ", topk[i]);// 最后使用完堆后記得釋放free(topk);
}

---

整體代碼展示

heap.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;// 以大堆為例
// 堆初始化
void HeapInit(Heap* php);
// 數(shù)組創(chuàng)建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n);// 插入數(shù)據(jù)
void HeapPush(Heap* php, HPDataType x);
// 刪除數(shù)據(jù)
void HeapPop(Heap* php);// 獲取堆頂數(shù)據(jù)
HPDataType HeapTop(Heap* php);// 獲取堆數(shù)據(jù)個數(shù)
int HeapSize(Heap* php);// 堆判空
bool HeapEmpty(Heap* php);// 堆的銷毀
void HeapDestroy(Heap* php);// 交換
void swap(HPDataType* a, HPDataType* b);
// 向上調(diào)整
void adjustup(HPDataType* a, int child);
// 向下調(diào)整
void adjustdown(HPDataType* a, int size, int parent);// 堆排序
void HeapSort(HPDataType* a, int n);
// topk問題
void PrintTopK(HPDataType* a, int n, int k);

heap.c

#include "heap.h"// 堆初始化
void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}
// 數(shù)組創(chuàng)建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n)
{assert(php && a);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");exit(-1);}memcpy(php->a, a, sizeof(HPDataType) * n);php->size = php->capacity = n;for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(php->a, n, i);
}// 插入數(shù)據(jù)
void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;adjustup(php->a, php->size - 1);
}
// 刪除數(shù)據(jù)，刪除堆頂?shù)臄?shù)據(jù)
void HeapPop(Heap* php)
{assert(php && !HeapEmpty(php));swap(&php->a[0], &php->a[php->size - 1]);php->size--;adjustdown(php->a, php->size, 0);
}// 獲取堆頂數(shù)據(jù)
HPDataType HeapTop(Heap* php)
{assert(php && !HeapEmpty(php));return php->a[0];
}// 獲取堆數(shù)據(jù)個數(shù)
int HeapSize(Heap* php)
{assert(php);return php->size;
}// 堆判空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}// 堆的銷毀
void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->capacity = php->size = 0;
}// 交換
void swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}
// 向上調(diào)整
void adjustup(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else break;}
}
// 向下調(diào)整
void adjustdown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] > a[child]) child++;if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else break;}
}// 堆排序
void HeapSort(HPDataType* a, int n)
{assert(a);// 向下調(diào)整, 這里是建大堆for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(a, n, i);// 排序（建的大堆就是升序）int k = n - 1;while (k > 0){swap(&a[0], &a[k]);adjustdown(a, k, 0);k--;}
}// topk問題
void PrintTopK(HPDataType* a, int n, int k)
{assert(a);HPDataType* topk = (HPDataType*)malloc(sizeof(HPDataType) * k);if (topk == NULL){perror("malloc fail");exit(-1);}memcpy(topk, a, sizeof(HPDataType) * k);// 找前k個最小的，建大堆for (int i = (k - 2) / 2; i >= 0; i--) adjustdown(topk, k, i);for (int i = k; i < n; i++){if (a[i] < topk[0]){topk[0] = a[i];adjustdown(topk, k, 0);}}for (int i = 0; i < k; i++) printf("%d ", topk[i]);free(topk);
}

test.c

#include "heap.h"void test1()
{Heap hp;HeapInit(&hp);HeapPush(&hp, 22);HeapPush(&hp, 122);HeapPush(&hp, 16);HeapPush(&hp, 45);HeapPush(&hp, 56);HeapPush(&hp, 18);HeapPush(&hp, 134);HeapPush(&hp, 99);HeapDestroy(&hp);
}void test2()
{Heap hp;HeapInit(&hp);int arr[] = { 34,113,78,44,98,99,35,26,18,68 };int n = sizeof(arr) / sizeof(arr[0]);HeapCreateArray(&hp, arr, n);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}printf("\n");HeapDestroy(&hp);
}void test3()
{int arr[] = { 34,113,78,44,98,99,35,26,18,68 };int n = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);for (int i = 0; i < n; i++) printf("%d ", arr[i]);printf("\n");
}void testTopK()
{int arr[] = { 34,113,78,44,98,99,35,26,18,68 };int n = sizeof(arr) / sizeof(arr[0]);PrintTopK(arr, n, 5);
}int main()
{//test1();test2();test3();testTopK();return 0;
}

寫在最后

💝
???🔥后續(xù)將會持續(xù)輸出有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法的文章，你們的支持就是我寫作的最大動力！

感謝閱讀本小白的博客，錯誤的地方請嚴(yán)厲指出噢~