1. 堆的概念及结构 🚀
2. 堆的实现 🚀
在实现堆有两个比较重要的事情就是理解向上调整算法和向下调整算法。
堆的向上调整算法：是为了在插入数据的时候使原来的结构不变，还是一个堆。
堆的向下调整算法：1.是为了建堆。或者给你一个数组这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，我们要通过算法，把它构建成一个堆。2.删除堆数据的时候要用向下调整算法。
2.1. 堆向下调整算法 🚀
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个 前提 ：左右子树必须是一个堆，才能调整。
2.2. 堆的创建 🚀
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过向下调整算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
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<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> #include<errno.h> #include<stdbool.h> #include<time.h> typedef 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); //堆排序 NLogN void 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 < n; ++i) php->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 < php->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] < a[root]) { Swap(&a[child], &a[root]); root = child; child = root * 2 + 1; } else { break; } } } // 堆的插入 void HeapPush(Heap* php, HPDataType x) { assert(php); if (php->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*LogN void 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); }
4.3. test.c 🚀
#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; }
最后的最后，创作不易，希望读者三连支持💖
赠人玫瑰，手有余香💖
