前言
作者：小蜗牛向前冲
名言：我可以接受失败，但我不能接受放弃
如果觉的博主的文章还不错的话，还请
点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。
一 堆
1 堆的概念
有一组数据，我们将他们用完全二叉树的方式储存在一个一维数组中，并满足一定规律。 则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2 堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
这里我们要区分堆在逻辑上是个树的形状，但是在物理层面上是挨着存储的。 
二 堆的实现
1 堆实现的功能
对于堆来是一般要实现入堆和出堆的功能,这里我们对于堆的建立很像顺序表，但他们仍然是有很大区别的，下面大家可以在堆的实现过程中细细体会。
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HPDataType; //定义堆 typedef struct heap { HPDataType* a; int size; int capacity; }HP; //打印 void HeapPrint(HP* php); //初始化 void HeapInit(HP* php); //销毁堆 void HeapDestroy(HP* php); // 入堆 void HeapPush(HP* php, HPDataType x); // 出堆顶元素 void HeapPop(HP* php); // 返回堆顶元素 HPDataType HeapTop(HP* php); //判断堆是否为空 bool HeapEmpty(HP* php); //求堆的大小 int HeapSize(HP* php); //向上调整 void ADjustDown(HPDataType* a, int n, int parant); //向下调整 void ADjustUp(HPDataType* a, int child); //交换 void swop(int* p1, int* p2);
2 向上调整算法和向下调整算法
在这里我们先来了解堆调整的二种算法：
向上调整算法
我们先说一个结论：
数组小标计算父子关系公式：
parant = (child-1)/2;
LeftChild = parant*2+1; 奇数
RightChild = parant*2+2; 偶数
好我们知道了，这个公式我们就可以通过数组建树 ，至于如何建堆，下面在说，我们继续可看到向上调整算法。
我们知道是通过数组来建堆，我们要插入一个数据，直接插入到数组的后一个元素这肯定是不符合堆的规则的，那么我们可以用向上调整算法来进行调整，调整的方式见上图（小堆）。
下面我们用代码来实现一下：
/向上调整 void ADjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { //小堆 if (a[parent] > a[child]) { //交换 swap(&a[parent], &a[child]); } else { break; } //向上调整 child = parent; parent = (child - 1) / 2; } }
那么我们在来思考一下，该算法的时间复杂度为都少呢？
假设我们认为数有N层，我们入堆一个数，最坏的结果是N-1次也就是，该算法的时间复杂度为O(N)。
向下调整算法
这个算法我们可用来解决出堆的问题，为什么这么说呢？因为每次我们出堆，我们都要保持堆的结构的完整性，那么我们就要选出最小或者最大的数做堆顶。
当我们要出堆时，只要让数组的首元素和最后的元素交换，在size--,在用向下调整算法就可以保持堆的结构的父子关系。
该算法的核心就是当在交换后，让首元素(父节点)和最小的子节点交换，以次类推得到小堆。
要想得到大堆只要改变：
把a[minChild]a[parant]即可。
代码实现如下：
void ADjustDown(HPDataType*a,int n,int parant) { int minChild = parant * 2 + 1; //找出最小的孩子 while (minChild < n) { if (minChild + 1 < n && a[minChild] > a[minChild + 1]) { minChild++; } if (a[minChild] < a[parant]) { //交换 swop(&a[parant], &a[minChild]); parant = minChild; minChild = parant * 2 + 1; } else { break; } } }
那该算法的时间复杂度又是多少呢？
我们假设该树有N层，总节点数为n：
第1层：有2^0个节点
第2层：有2^1个节点
第3层：有2^2个节点
…………………………
第N层:有2^(N-1)个节点
从中可以看出这就是个等比数列，所以我们直接通过公式求和：
T(N)=2^N-1,对于该算法最坏的结果就是每层都要调整，则n = 2^N-1，所以时间复杂度为
N = log(n+1),即为O(logn)
综上说：
向上调整算法的时间复杂度为O(n),而向下调整法的时间复杂度为O(logn),也就是向下调整算法的效率是更高的。
3 实现堆
堆的初始化
//初始化堆 void HeapInit(HP* php) { assert(php);//断言 php->a = NULL; php->size = php->capacity = 0; }
在入堆和出堆的过程中我们都次要用到交换这个功能，所以我们在这里去实现个交换功能
//交换 void swop(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; }
堆的销毁
//堆的销毁 void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->capacity = php->size = 0; }
入堆
这里用到了向上调整算法，上面我们知道向下调整算法是比向下调整更优的，所以说我们这里是可以改进的。
void HeapPush(HP* 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; php->size++; //向上调整保持堆的形状 ADjustUp(php->a, php->size - 1); }
出堆顶元素
//出堆顶元素 void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); //交换 swop(&php->a[0], &php->a[php->size - 1]); php->size--; //向下调整 ADjustDown(php->a,php->size,0); }
返回堆顶元素
//返回堆顶元素 HPDataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; }
判断堆是否为空
bool HeapEmpty(HP* php) { assert(判断堆是否为空php); return php->size == 0;//为空返回true,不为空返回flase }
返回堆的长度
//返回堆的长度 int HeapSize(HP* php) { assert(php); return php->size - 1; }
完整实现：
#define _CRT_SECURE_NO_WARNINGS #include"heap.h" //打印堆 void HeapPrint(HP* php) { assert(php); int i = 0; while (php->size > i) { printf("%d ", php->a[i]); ++i; } printf("\n"); } //初始化堆 void HeapInit(HP* php) { assert(php);//断言 php->a = NULL; php->size = php->capacity = 0; } //交换 void swop(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整 void ADjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { //小堆 if (a[parent] > a[child]) { //交换 swop(&a[parent], &a[child]); } else { break; } //向上调整 child = parent; parent = (child - 1) / 2; } } //堆的销毁 void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->capacity = php->size = 0; } // 入堆 void HeapPush(HP* 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; php->size++; //向上(或者向下)调整保持堆的形状 ADjustDown(php->a, php->size, 0); } void ADjustDown(HPDataType*a,int n,int parant) { int minChild = parant * 2 + 1; //找出最小的孩子 while (minChild < n) { if (minChild + 1 < n && a[minChild] > a[minChild + 1]) { minChild++; } if (a[minChild] < a[parant]) { //交换 swop(&a[parant], &a[minChild]); parant = minChild; minChild = parant * 2 + 1; } else { break; } } } //出堆顶元素 void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); //交换 swop(&php->a[0], &php->a[php->size - 1]); php->size--; //向下调整 ADjustDown(php->a,php->size,0); } //返回堆顶元素 HPDataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; } //判断堆是否为空 bool HeapEmpty(HP* php) { assert(php); return php->size == 0;//为空返回true,不为空返回flase } //返回堆的长度 int HeapSize(HP* php) { assert(php); return php->size - 1; }
三 堆的应用
对于堆来是主要用途：
堆排序
解决TOP-K问题
1 堆排序
为什么说堆可用来排序呢？我们知道堆顶一定是这堆中最大数或者最小数，所以我们可以利用这一特性进行排序。
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
建堆
升序：建大堆
降序：建小堆
对于建堆来说，我们可以去写一个堆，但这样太麻烦了，我们可以直接通过向下调整算法建堆。
我们假设树的高度为h
第1层，2^0个节点，需要向下移动h-1层
第2层，2^1个节点，需要向下移动h-2层
第3层，2^2个节点，需要向下移动h-3层
第4层，2^3个节点，需要向下移动h-4层
………………………………………………
第h-1层，2h-2个节点，需要向下移动1层
调整次数 = 每一次层节点个数*这层最坏向下调整的次数
我们建堆的时间复杂度我们可以通过计算得：
所以说向下调整建堆的时间复杂度为O(N)。
利用堆删除思想来进行排序
其实就是建堆尾和堆头交换，后通过向下调整算法，将最大数或者最小数倒序排出。
完整代码：
//思路：依次选择数，从后往前排 // 升序------大堆 // 降序------小堆 //堆排 void HeapSort(int* a, int n) { //从下调整建堆 for (int i = (n - 2) / 2;i >= 0;--i) { ADjustDown(a, n, i); } //交换，选数 int i = 1; while (i < n) { swop(&a[0], &a[n - i]); ADjustDown(a, n - i,0); ++i; } }
oj场景：
代码实现：
class Solution { public: //向下调整 void adjust_down(vector<int>& st, int parent) { int n = st.size(); int child = parent * 2 + 1;//当前节点，左孩子的索引 while (child < n) { //找出当前节点中较大大节点 if (child + 1 < n && st[child] < st[child + 1])//child+1<n防止出现右孩子不存在的情况 { child++; } if (st[child] > st[parent])//孩子大于父亲 { //交换 swap(st[child], st[parent]); //更新父亲节点 parent = child; //更新当前节点，左孩子的索引 child = parent * 2 + 1; } else { break;//满足大堆的情况不必调整 } } } //向上调整 void adjust_up(vector<int>& st, int child) { int n = st.size(); int parent = (child - 1) / 2; //这里应该用孩子节点来判断调整，如果用父节点(child-1)/2，当child==0，parent=0>=0 //如果以父亲<0作为循环终止条件是判断不出来的 while (child > 0) { if (st[child] > st[parent]) { swap(st[child], st[parent]); child = parent; parent = (child - 1) / 2; } else break; } } int getMax(vector<int>& st) { int ret = st[0]; int n = st.size(); swap(st[0], st[n - 1]);//将堆顶元素和堆尾元素交换 st.pop_back();//出堆顶元素 adjust_down(st, 0);//从堆顶元素开始向下调整 return ret; } int lastStoneWeight(vector<int>& stones).0 { int n = stones.size(); //通过向下调整法进行建堆 //i = (n-2)/2表示是最后一个非叶子节点 for (int i = (n - 2) / 2; i >= 0; i--) { adjust_down(stones, i); } //进行模拟即可 int x = 0, y = 0; while (stones.size() > 1) { y = getMax(stones); x = getMax(stones); if (x < y) { stones.push_back(y - x);//在堆的最后插入元素 adjust_up(stones, stones.size() - 1); } } return stones.size() == 0 ? 0 : stones.front(); } };
总结：
1、在建堆的时候最好用向下调整法：时间复杂度为O(N)。
2、向堆中插入元素(数组最后)，用向上调整法
3、在出堆顶元素后，用向下调整法
在向堆中插入元素和在出堆顶元素后进行调整时，采用不同的调整方法可以提高效率的原因如下：
- 向上调整法的效率高于向下调整法的原因：
- 插入元素时，通过向上调整法可以在将新元素放入堆的合适位置上进行逐步比较和交换。由于新元素是在堆的末尾插入的，所以需要进行的比较和交换的次数较少，我们只需要比较新元素与其父节点的大小关系，并进行交换直到满足堆的性质为止。这样的操作次数较少，可以更快地将新元素放置到正确的位置上，因此向上调整法在插入元素时较高效。
- 向下调整法的效率高于向上调整法的原因：
- 在出堆顶元素后，需要将新的顶部元素下移到正确的位置上以保持堆的性质。通过使用向下调整法，我们可以将顶部元素逐步与其子节点进行比较，并选择与之交换的合适子节点，直到满足堆的性质为止。相较于向上调整法，在向下调整法中，我们可以通过一次交换将新的顶部元素下移到正确的位置，而不需要进行多次交换。这种操作方式减少了比较和交换的次数，因此向下调整法在堆顶元素出堆后较高效。
2 TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
如求世界最高10人的身高，我们第1个想法是世界上所以的人的身高都排序个序，但这样是不是代价太大了，那我们有没有更加简单的方法呢？这将可以用到我们的堆了。
用数据集合的前K个元素来建堆：
前K个最大元素，建小堆
前K个最小元素，建大堆
堆中选数
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
完整代码：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<time.h> typedef int HPDataType; //定义堆 typedef struct heap { HPDataType* a; int size; int capacity; }HP; //交换 void swop(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整算法 void ADjustDown(HPDataType* a, int n, int parant) { int minChild = parant * 2 + 1;//默认左孩子是最小 //找出最小的孩子 while (minChild < n) { if (minChild + 1 < n && a[minChild] > a[minChild + 1]) { minChild++; } if (a[minChild] < a[parant]) { //交换 swop(&a[parant], &a[minChild]); parant = minChild; minChild = parant * 2 + 1; } else { break; } } } //创建数据 void CreateDataFile(const char* filename, int N) { //以写入的方式打开文件 FILE* fin = fopen(filename, "w"); if (NULL==fin) { perror("fopen fail"); return; } srand(time(0)); //写入数据 for (int i = 0;i < N;++i) { fprintf(fin, "%d\n", rand() % 1000000); } fclose(fin); } //TOP前10位数 void PrintTopK(const char* filename, int k) { assert(filename); //打开文件 FILE* fout = fopen(filename, "r"); if (NULL==fout) { perror("fopen fail"); return; } //为堆分配空间 int* minHeap = (int*)malloc(sizeof(int) * k); if (NULL == minHeap) { perror("malloc fail"); return; } //读取前K个元素 for (int i = 0;i < k;++i) { fscanf(fout, "%d", &minHeap[i]); } //建出小堆 for (int i = (k - 2) / 2; i >= k;--i) { ADjustDown(minHeap, k, i); } //比较后N-K个元素比堆顶元素大的就入堆 int val = 0; while (fscanf(fout, "%d", &val) != EOF) { if (val > minHeap[0]) { minHeap[0] = val; ADjustDown(minHeap, k, 0); } } //打印排序结果 for (int i = 0;i < k;++i) { printf("%d ", minHeap[i]); } //释放空间 free(minHeap); //关闭文件 fclose(fout); } int main() { const char* filename = "Date.txt"; int N = 1000000; int k = 10; //CreateDataFile(filename, N); PrintTopK(filename, k); return 0; }
在这里博主遇到了一个BUG想了很久，想和大家分享一下；
报了个断错误，我调试到90行代码时报错，我想这里这么会错误，断错误一般是传了个空参数
，我一想我就往上看，看一眼(我没错啊，我这么会错呢），就这样倒腾了半天。 
突然发现，自己将fout置空了。
这样的问题大家都有遇到到吧！那我们有上面方式避免吗？
其实有的，我们可以这样写。 
如果我们仍然把等于(==)写成了赋值(=)会这么样呢？
这样编译就不会通过，这样我就能及时是发现问题并解决。
