目录 

1. 堆的概念及结构 🚀

2. 堆的实现 🚀

2.1. 堆向下调整算法 🚀

2.2. 堆的创建 🚀

2.4. 堆的插入 🚀

2.5. 堆的删除 🚀

3. 堆的应用 🚀

3.1 堆排序 🚀

3.2 TOP-K问题 🚀

注意 

4. 源代码 🚀

4.1. Heap.h 🚀

4.2. Heap.c 🚀

4.3. test.c 🚀

hello✨，大家好呀，这里是原来💖 💛💙随着文章篇幅越来越多可能有很多小伙伴们找不到自己想要看的文章🎁 🎁 🎁C语言的入门篇进阶篇和深剖篇都整理在这里了哈。然后这里是个人主页，比点头像更好找文章哈。🎈 🎈🎈 

---

作者新建立的社区：非科班转码社区-CSDN社区云💖💛💙

期待hxd的支持哈🎉 🎉 🎉

这里附带作者qq：2777137742

                      vx：q2777137742

因为私信消息很多不容易看见哈

---

最后是打鸡血环节：改变的确很难，但结果值得冒险，拿出点勇气来。路还很长，现在才刚开始而已。过去无可挽回，未来可以改变。🚀 🚀 🚀

1. 堆的概念及结构 🚀

还有堆的左右子树都是大堆或者小堆，堆顶是最大值或者最小值。

2. 堆的实现 🚀

在实现堆有两个比较重要的事情就是理解向上调整算法和向下调整算法。

堆的向上调整算法：是为了在插入数据的时候使原来的结构不变，还是一个堆。

堆的向下调整算法：1.是为了建堆。或者给你一个数组这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，我们要通过算法，把它构建成一个堆。2.删除堆数据的时候要用向下调整算法。

2.1. 堆向下调整算法 🚀

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个 前提 ：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

2.2. 堆的创建 🚀

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过向下调整算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

2.3. 建堆时间复杂度 🚀

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：

2.4. 堆的插入 🚀

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。（数据从下往上调，所以是向上调整算法）

2.5. 堆的删除 🚀

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

3. 堆的应用 🚀

3.1 堆排序 🚀

堆排序即利用堆的思想来进行排序，总共分为两个步骤： 1. 建堆 升序：建大堆 降序：建小堆2. 利用堆删除思想来进行排序（时间复杂度：NLogN 和 qsort一个等级哈） 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

3.2 TOP-K问题 🚀

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。 比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100的活跃玩家等。 对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下： 1. 用数据集合中前 K 个元素来建堆 前 k 个最大的元素，则建小堆 前 k 个最小的元素，则建大堆 2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 

注意 

上面说的所有，如果不太理解，我们直接看下面的代码，作者是认为一个程序员代码可能给你的理解要比大白话要更直接哈。

4. 源代码 🚀

这里作者是建的小堆，如果要建大堆就改作者在代码里面声明的地方，就把三个小于改成大于就可以了哈。

源代码里面解决了：建堆（给一个数组建堆），堆的各项操作，堆排序，TopK问题。 

PS:代码里面有详细的解释哈。

main函数里面test1里面是建堆的各项操作的测试及堆排序的测试。

                      test2里面是给一个数组然后建堆的测试哈。

4.1. Heap.h 🚀

#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include#include#include#includetypedef int HPDataType;typedef struct Heap{HPDataType* a;size_t size;size_t capacity;}Heap;//初始化void HeapInit(Heap* php);//打印void HeapPrint(Heap* php);// 堆的构建void HeapCreate(Heap* php, HPDataType* a, int n);// 堆的销毁void HeapDestory(Heap* php);// 堆的插入void HeapPush(Heap* php, HPDataType x);// 堆的删除void HeapPop(Heap* php);// 取堆顶的数据HPDataType HeapTop(Heap* php);// 堆的数据个数size_t HeapSize(Heap* php);// 堆的判空bool HeapEmpty(Heap* php);//堆排序  NLogNvoid HeapSort(int* a, size_t size);// TopK问题：找出N个数里面最大/最小的前K个问题。// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，// 需要注意：// 找最大的前K个，建立K个数的小堆// 找最小的前K个，建立K个数的大堆void PrintTopK(int* a, int n, int k);void TestTopk();

4.2. Heap.c 🚀

#define _CRT_SECURE_NO_WARNINGS 1#include"Heap.h"void AdjustDown(HPDataType* a, size_t sz, size_t root); 堆的构建//void HeapCreate(Heap* php, HPDataType* a, int n)//{//assert(php);//HPDataType* new = (HPDataType*)malloc(sizeof(HPDataType) * n);//if (new == NULL)//{//perror("HeapCreate failed!\n");//exit(-1);//}//php->a = new;//php->capacity=n;//php->size = 0;//int curpos = php->size / 2 - 1;//while (curpos >= 0)//{//AdjustDown(php->a, 7,curpos);//curpos--;//}//}//给数组建堆void HeapCreate(Heap* php, int arr[], int n){php->a = (int*)malloc(sizeof(HPDataType) * n);assert(php->a != NULL);php->capacity = n;php->size = n;//先把数据进堆for (int i = 0; i a[i] = arr[i];//先找到最后一个分支的第一个非叶子节点  int curpos = php->size / 2 - 1;while (curpos >= 0){AdjustDown(php->a, 7,curpos);curpos--;}}//初始化void HeapInit(Heap* php){assert(php);php->a = NULL;php->capacity = 0;php->size = 0;}//打印void HeapPrint(Heap* php){assert(php);assert(php->size > 0);for (size_t i = 0; i size; i++){printf("%d ", php->a[i]);}printf("\n");}// 堆的销毁void HeapDestory(Heap* php){assert(php);php->a = NULL;php->capacity = 0;php->size = 0;free(php->a);}//交换void Swap(HPDataType* p1, HPDataType* p2){HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}//小堆为例  大堆换符合就可以了//向上调整算法void AdjustUP(HPDataType* a, size_t child){size_t parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);}else{break;}child = parent;parent= (child - 1) / 2;}}//向下调整算法void AdjustDown(HPDataType* a, size_t sz, size_t root){//先找左右小的孩子//再和root的比  比root小就交换//root等于那个要交换的孩子 孩子再选  然后迭代//改为这个可能更好看一点//size_t parent = root;//这里默认左孩子//size_t child = parent * 2 + 1;//这里默认左孩子size_t child = root * 2 + 1;//sz的作用就是确保左右还在在数组内while (child<sz){//小心右孩子不存在//找左右孩子小的//还有注意要把比较左右孩子放进循环，因为每次都要比较if (child+1<sz && a[child + 1] < a[child]){child = child + 1;}if (a[child] capacity == php->size){size_t newcapacity = php->capacity == 0 ? 4 : php->capacity*2;HPDataType* new = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (new == NULL){printf("%s", strerror(errno));exit(-1);}php->a = new;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;//上面是插入数据   //下面是 向上调整算法 使插入数据后还是一个小堆AdjustUP(php->a,php->size-1);}// 堆的删除void HeapPop(Heap* php){assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//传参注意一下 AdjustDown(php->a,php->size,0);}// 取堆顶的数据HPDataType HeapTop(Heap* php){assert(php);assert(php->size > 0);HPDataType top = php->a[0];return top;}// 堆的判空bool HeapEmpty(Heap* php){assert(php);return php->size == 0;}// 堆的数据个数size_t HeapSize(Heap* php){assert(php);return php->size;}//现在默认小堆，想变为大堆就把上面的向上向下调整算法改一下判断就可以了(3个)//堆排序时间复杂度:  NLogN//为什么是NLogN:因为每次插入数据都是一层只插入一个数据(假设是满二叉树,总// 节点个数就是2^k-1:(2^(k-1)*2-1/(2-1))=N)，k=Log2(k+1),即LogN)// 又因为有N个数要排//所以就是N*LogNvoid HeapSort(int* a, size_t size){assert(a);Heap hp;HeapInit(&hp);size_t i = 0;for (i = 0; i < size; i++){HeapPush(&hp, a[i]);}while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestory(&hp);}// TopK问题：找出N个数里面最大/最小的前K个问题。// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，// 全国排名前10的李白。等等问题都是Topk问题，// 需要注意：// 找最大的前K个，建立K个数的小堆// 找最小的前K个，建立K个数的大堆void PrintTopK(int* a, int n, int k){assert(a);assert(k < n);Heap hp;HeapInit(&hp);int i = 0;for (i = 0; i < n; i++){HeapPush(&hp, a[i]);}while (k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);}}void TestTopk(){//int arr[] = { 15,18,19,25,28,34,65,49,27,37 };//int sz = sizeof(arr) / sizeof(arr[0]);//int k = 5;//PrintTopK(arr, sz, k);int n = 10000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));for (size_t i = 0; i < n; ++i){a[i] = rand() % 1000000;}a[5] = 1000000 + 1;a[1231] = 1000000 + 2;a[531] = 1000000 + 3;a[5121] = 1000000 + 4;a[115] = 1000000 + 5;a[2335] = 1000000 + 6;a[9999] = 1000000 + 7;a[76] = 1000000 + 8;a[423] = 1000000 + 9;a[3144] = 1000000 + 10;PrintTopK(a, n, 10);}

#define _CRT_SECURE_NO_WARNINGS 1#include"Heap.h"void test1(){//Heap hp;//HeapInit(&hp);HeapCreate(&hp, arr, 10);//HeapPush(&hp, 1);//HeapPrint(&hp);//HeapPush(&hp, 5);//HeapPrint(&hp);//HeapPush(&hp, 0);//HeapPrint(&hp);//HeapPush(&hp, 8);//HeapPrint(&hp);//HeapPush(&hp, 3);//HeapPrint(&hp);//HeapPush(&hp, 9);//HeapPrint(&hp);//HeapPush(&hp, 17);//HeapPrint(&hp);//HeapPush(&hp, 13);//HeapPush(&hp, 15);//HeapPush(&hp, 20);//HeapPrint(&hp);//printf("size=%d \n", HeapSize(&hp));//while (!HeapEmpty(&hp))//{//printf("%d ", HeapTop(&hp));//HeapPop(&hp);//}//HeapDestory(&hp);/// ////升序int arr[] = { 15,18,19,25,28,34,65,49,27,37 };size_t sz = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, sz);//TestTopk();}void test2(){Heap hp;HeapInit(&hp);int arr[] = { 3,7,5,2,9,10,15 };HeapCreate(&hp, arr, 7);for (int i = 0; i < 7; i++){printf("%d ", hp.a[i]);}}int main(){test1();    //test2();return 0;}

体育科学