目录
一.堆的定义
二.堆的函数介绍与实现
1.堆的结构
2.HeapInit(堆的初始化)
3.HeapDestroy（堆的摧毁）
4.HeapPush(往堆里面插入元素)
5.HeapPrint(打印堆里面的元素)
6.HeapPop(将堆顶元素弹出)
7.HeapTop(取堆顶元素)
8.HeapSize(返回堆的大小)
9.HeapEmpty(判断堆是否为空)
10.HeapCreate(创建一个堆)
1.向上调整建堆
2.向下调整建堆
3.两种建堆方式的时间复杂度对比
4.总结
三.堆的应用
1.堆排序（HeapSort）
2.topK问题
一.堆的定义
堆是以数组的方式实现，通过父结点和子结点之间的关系，来构建的一棵完全二叉树.
大堆:父结点的值都大于其子结点的值，比如说下面这棵完全二叉树
父亲(70)大于它的两个孩子(56，34)，以此类推，父亲(56)大于它的两个孩子(38,27).
小堆:父结点的值都小于其子结点的值，比如说下面这棵完全二叉树
父亲(10)小于它的两个孩子(28，37)，以此类推，父亲(28)小于它的两个孩子(34，78).
既然堆是一棵完全二叉树，而且以数组的形式存储，这也就意味着，它父亲和孩子之间的下标实
际上是有关联的.
我们拿上面大堆的例子进行举例
左边是我们所想的逻辑结构，而右边是在内存中实际存储的物理结构(数组).
我们可以观察到38，27(孩子)的下标，先减1，再除以2，刚好是56(父亲)的下标.
而相应的 56(父亲)的下标1,乘2加1，可以得到它左孩子(38)的下标3
乘2加2，可以得到它右孩子(27)的下标4
实际上，这个规律可以进一步推广到所有的堆
二.堆的函数介绍与实现
1.堆的结构
现在我们就可以开始从0开始构建一个堆.
首先把需要包含的头文件全部包含.
和顺序表完全相同，我们用一个结构体来表示堆，只是命名有所不同而已.
size用来记录堆中一共有多少个元素，capacity是我们开辟给数组的空间，当空间不够的时候，用
realloc重新开辟空间，这些操作都和顺序表相同，这里不多解释.
2.HeapInit(堆的初始化)
//堆的初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}3.HeapDestroy（堆的摧毁）
//堆的摧毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}4.HeapPush(往堆里面插入元素)
我们依旧拿前面的大堆举例子，假设现在来了一个新的数字12.
我么把它放到数组的最后面，可以发现，刚刚好，这个数组依旧可以保持一个大堆.
它的父亲(34)依旧大于左孩子(12).
但是，这并非是绝对的，假如来了一个新的数字81.
比如下图所示，则这个数组很明显就不再是一个大堆了.
所以，我们在插入一个元素的时候，除了要考虑插入问题外(是否要扩容?然后新元素直接放到最后)，还需要考虑调整问题.
一个有效的方法是向上调整.（AdjustUp）
我们可以发现，即便插入一个新的元素会破坏原来的堆，但它会影响它的祖先.
比如下图的蓝色圈圈里面的数，它依旧保持一个大堆.
因此，我们只需要将新插入的数(81)，沿着它祖先，逐一进行调整，直到最后形成一个大堆，便可
以停止.
总体的思路是，不断循环，通过孩子的下标，我们可以得到它父亲的下标[parent = (child - 1)/2]，
将孩子的值和父亲的值进行比较.
如果孩子的值比父亲的值大，则交换两个数；否则，跳出循环.
由于交换两个数的代码后续会经常使用，所以我们也可以把它单独分装成一个函数出来.
//交换两个元素
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]){Swap(&a[child], &a[parent]);//调整坐标，并计算新的父亲的下标，判断是否需要进一步调整child = parent;parent = (child - 1) / 2;}else{ //孩子小于父亲，跳出循环break;}}
}当然，这里是建大堆的向上调整代码示范，如果是建小堆，只需要将判断孩子大于父亲，改为孩子
小于父亲即可.
而且由于孩子只会和祖先进行比较，它的时间复杂度只和树高有关，即它的时间复杂度为O(logN).
实现完AdjustUp后，那往堆里面插入元素，总体的思路，我们已经理清楚.
第一步，判断数组是否需要扩容
第二步，往数组里最后一个位置插入新元素
第三步，向上调整，建成新堆.
//往堆里面插入元素
void HeapPush(HP* php, HPDataType x)
{assert(php);//考虑是否需要扩容if (php->capacity == php->size){//由于初始化的时候，未指定空间大小，所以若php->caapacity == 0，则初始化开辟一个//4个元素的空间即可.int newcapacity = php->capacity == 0 ? 4: php->capacity *2;int * tmp = realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail.\n");exit(-1);}php->a = tmp;php->capacity = newcapacity;}//末尾插入元素，同时调整sizephp->a[php->size] = x;php->size++;//向上调整，注意最后一个数的下标是size - 1AdjustUp(php->a,php->size-1);
}5.HeapPrint(打印堆里面的元素)
//打印堆
void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}6.HeapPop(将堆顶元素弹出)
对于一个堆来说，堆顶元素有着重要的意义.
对于大堆来说，堆顶的元素，它一定是整个堆(数组)里面的最大值.
对于小堆来说，堆顶的元素，它一定是整个堆(数组)里面的最小值.
比如这样一个大堆，65(堆顶元素)，一定是整个堆中最大的数.
利用这个性质，我们可以实现堆的应用——PopK问题.
当然在这之前，我们还需要解决HeapPop函数(将堆顶元素弹出后，仍然保证它是一个堆的难题.
依旧拿上面的大堆举例，假设我们要取出65，一个简单的想法，就是将65后面的数字全部往前移
动.
但仔细思索，我们就会发现这根本行不通.
第一，时间复杂度是O(N),假如数据非常多，时间消耗还是比较大的.
第二，移走65后，剩下的数字，根本不是一个堆.
37明显比34大，这显然不是一个大堆.
为了解决这个问题，我们必须思考出现这种现象的原因是什么.
之所以会出现上述两个问题，第一个原因是数组的头删，本身效率就不高，真正效率高的，是尾删
第二个原因是向前移动，虽然空间相对位置并没有改变，但改变了原来数组数字的相对逻辑位置.
原本49和34是一对好兄弟，结果49却背叛了39，他一直想当34的爸爸.这显然是不行的.
所以我们将堆顶元素(65)，和堆最后的一个元素(18)互换.
那这时候，我们再删除65，也就非常轻松，进行的正好就是尾删的操作.
同时，也保证了原来堆中数字的相对逻辑位置不变.（左边仍然是一个堆，右边也仍旧是一个大
堆）
现在我们可以抽象出这样的一种结构，只需要把它变成堆即可.
类比AdjustUp的思路，我们可以设计出AdjustDown函数.
左堆的堆顶元素，一定是左堆中最大的数；右堆的堆顶元素，也一定是右堆最大的数.
我们一直循环，直到超出堆的长度或者不需要再调整为止(孩子小于父亲).
每次循环进行这样的操作.
第一步，找出左堆和右堆中，较大的数
第二步，和我们的数字(原来堆末尾的数字)进行交换.
49是较大的数，将18和49交换.
37是较大的数，将18和37交换.
然后我们就可以构建一个新的大堆，并且时间复杂度也是只和树的高度相关，为O(logN).
//向下调整
void AdjustDown(HPDataType * a, int size, int parent)
{ int child = (parent * 2) + 1;//a[size]并不是堆中的元素，所以循环不需要加等于while (child < size){//先判断右孩子是否存在，若存在判断其是否大于左孩子if (child + 1 < size && a[child] < a[child + 1]){//若大于左孩子，则右孩子为较大值.child++;}//比较孩子if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = (parent * 2) + 1;}else{break;}}
}实现完AdjustDown后，我们也基本理清HeapPop函数的实现思路.
第一步，判断数组是否是空
第二步，将堆顶元素和堆最后一个元素互换
第三步，向下调整，建成新堆.
//弹出堆顶元素
void HeapPop(HP* php)
{assert(php);//判断堆是否为空,无元素则可以直接报错assert(php->size > 0);//将堆中的第一个元素，和最后一个元素进行交换.Swap(&php->a[0], &php->a[php->size - 1]);//向下调整AdjustDown(php->a, php->size, 0);
}7.HeapTop(取堆顶元素)
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}8.HeapSize(返回堆的大小)
//堆大小
int HeapSize(HP* php)
{assert(php);return php->size;
}9.HeapEmpty(判断堆是否为空)
//堆的判空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}10.HeapCreate(创建一个堆)
PS：下面讨论的前提，都是默认会给你一堆数据，也就是一个数组，让你利用这些数据建堆.
否则，我们就需要手动自己进行录入数据.
1.向上调整建堆
我们前面其实已经介绍过HeapPush函数，通过它，我们其实就可以实现建堆的操作.
假设给了我们这样一个数组array（27，15，19，18，34，65，49，25，37）
现在我们要对其进行相应的调整，使之变成堆.
而HeapPush函数，本身的功能就是插入一个新的元素，并且把这堆数据调整成新堆.
所以，我们很容易就想到
把数组第一个元素放进堆里(一个数据也是堆)，然后遍历数组，逐一HeapPush每个元素即可建堆.
具体过程，可以看下面的图进一步理解.
//创建堆(向上调整建堆)
void HeapCreate(HP* php , HPDataType* a , int size)
{assert(php);HeapInit(php);for (int i = 0; i < size; ++i){HeapPush(php, a[i]);}
}2.向下调整建堆
那可不可以，直接对这个数组进行建堆呢?
答案是可以的，利用的恰好是我们前面提到过的AdjustDown函数.
之前我们提到过这样的一种结构，我们将采取同样的思路进行建堆.
假如左边是堆，右边也是堆，那我们就可以用AdjustDown函数，将其调整为一个新堆.
那假如左边不是堆呢?
那其实就可以把它看作一个新的任务，而这个建堆任务在结构上是和之前完全相同的.
28和37不是一个大堆，那就用AdjustDown调整为一个大堆.
18，49，25不是一个大堆，那就用AdjustDown调整为一个大堆.
19，34，65不是一个大堆，同样的用 AdjustDown调整为一个大堆.
...
以此类推最后就可以将数组调整为一个堆.
有意思的是，我们并不需要从最后一个元素开始向下调整建堆.
叶子结点一定是一个堆，我们只需要从堆中最后一个结点的父亲开始调整即可.
//创建堆(向下调整建堆)
void HeapCreate(HP* php, HPDataType* a, int size)
{assert(php);HeapInit(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * size);if (php->a == NULL){perror("malloc fail.\n");exit(-1);}//把需要建堆的数组直接拷到堆里memcpy(php->a, a, sizeof(HPDataType)*size);//记得及时调整堆的容量和数据个数php->capacity = php->size = size;//从堆中最后一个元素的父亲开始调整for (int i = (size - 1 - 1)/2; i >= 0; --i){AdjustDown(php->a, size, i);}
}3.两种建堆方式的时间复杂度对比
按我们的直觉理解，无论是向上还是向下调整，时间复杂度都是O(LogN)
然后有n个数，则建堆的时间复杂度都是O(NlogN).
但实际上并非如此.(下面的讨论都是用完美二叉树进行讨论，讨论最坏时间复杂度,即需要移动的
最大次数)
我们先看向下调整建堆.
向下调整建堆，是从第h-1层开始调整(堆中最后一个元素的父亲)，该层有个元素，每个元素最
多需要移动1次.
第h-2层有个元素，每个元素最多需要移动2次.
...
以此类推，第2层有个元素，每个元素最多需要移动(h - 2)次.
第1层有1个元素，每个元素最多需要移动(h - 1)次.
全部加起来，即为需要移动的最多次数.
利用错位相减进行化简，再根据树高和结点个数的关系(式3)
即可得到最坏时间复杂度O(N).
接下来，我们看向上建堆.
从第2层开始向上调整，总共有个元素，每个元素最多需要移动1次
...
第h-2层有个元素，每个元素最多需要移动(h - 2)次.
第h-1层有个元素，每个元素最多需要移动(h - 1)次.
由于我们知道，最后一层所移动的总次数绝对是最多的，无论是结点个数，还是移动次数.
因此我们可以直接对最后一项估算，即可得到向上调整的时间复杂度，而不需要再用错位相减法进
行计算.
所以，向上调整建堆，时间复杂度是O(NlogN).
为什么会出现这种现象呢？
从推理的过程其实我们也可以知道原因，就是因为最后一层的结点个数最多，几乎占据一半.
而向下调整，刚好跳过了最后一层，所以移动次数就会大大减少.
4.总结
向上建堆，是从一棵小树，逐渐长成一棵大树.
向下建堆，是将几棵小树，逐渐合成一棵大树.
这个思想后续我们也会遇到.
三.堆的应用
1.堆排序（HeapSort）
堆排序，进行的首先是建堆，毕竟我们操作的对象就是一个堆.
这里我们采用向下建堆的方式(时间复杂度较小，为O(N)).
那假如我们要升序，是建大堆还是小堆呢？
假如是小堆，那堆顶元素，就是升序排列后，相应的位置.
但后面的元素，又要重新建堆，假设向下建堆，那时间复杂度也是O(N),有n个数，则时间复杂度
是O(N^2)，那还不如直接用冒泡排序或者插入排序.
所以升序要用大堆
我们可以借鉴HeapPop函数的思想，将堆顶元素，放到数组的最后(也就是正确位置)
然后对堆顶元素向下调整建堆，使除了排好的元素外的元素成为一个新堆，时间复杂度为O(logN).
调整N - 1次(剩下一个元素的时候，不需要调整),时间复杂度便为O(NlogN).
总的时间复杂度为O(N + NlogN)，近似可以看作O(NlogN).
//堆排序
void HeapSort(HPDataType* a, int size)
{//向下调整建堆for (int i = (size - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, size, i);}//end始终指向需要建的堆中最后一个元素int end = size - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}同样的，如果需要降序的话，要用小堆.
2.topK问题
假设有一堆数据，总共N个，我们从中找出前K个最大的数，就被称为我们的topK问题.
这类问题在生活中其实非常常见，比如确定全世界几十亿人口中，最有钱的前十个人(乔布斯排行
榜)，全省高考分数前十名(高考状元).
这个时候，采取先对所有数据排序，然后打印前k个数，显然就不现实.
而我们采取堆这种数据结构，就可以巧妙解决这个问题.
假设我们要在N个数据中(N >>>>>> K)找前K个最大的数，采取的主要思路如下：
我们先把一堆数据中的前K个数，建成小堆.
然后逐一遍历所有的数据，比堆顶数据大，就入堆，并且向下调整，成为一个新堆.
当所有数据遍历结束后，我们建的小堆里面放的数，就是前K个最大的数.
为什么这样的方式可以呢？
由于小堆堆顶的元素，必然存放整个堆中最小的数，如果不是前K个最大的数,堆顶的元素就一定会
被替掉.
它的时间复杂度是多少呢？
K个数建小堆，时间复杂度是O(K)
假设剩下的N - K个数升序排列，则每次都需要和堆顶元素交换，并向下调整.
所以总的时间复杂度为O(K + (N - K)*logK),近似可以看作O(N)
空间复杂度就是O(K).
由于N非常大，所以我们只能将其存进磁盘中，这里模拟采用的是建立相应的txt文件.
随后，第一步便是在文件中产生相应的随机数.
这里我们调用rand函数来随机产生随机数，但为了保证随机数每次产生都不一样，所以还要搭配
srand,time函数来使用.
//数据先假设为10000个int n = 10000;int k = 5;srand((size_t)time(0));//造数据FILE* fin = fopen("Data.txt", "w");if (fin == NULL){perror("fopen fail.\n");exit(-1);}for (int i = 0; i < n; ++i){int val = rand();fprintf(fin, "%d\n", val);}fclose(fin);第二步，便是将前k个数，建成小堆.（采用向下调整的方式）
//将前k个数建成一个小堆int minHeap[5];FILE* fout = fopen("Data.txt", "r");if (fout == NULL){perror("fopen fail.\n");exit(-1);}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//向下调整建小堆for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDown(minHeap, k, i);}第三步，便是逐一遍历数据，假如比堆顶数据大，则交换堆顶元素，同时向下调整，建立新堆.
//逐一遍历数据，找出最大的数int val = 0;while (fscanf(fout, "%d", &val) != EOF){if (val > minHeap[0]){minHeap[0] = val;AdjustDown(minHeap, k, 0);}}fclose(fout);完整代码如下:
//测试N个数中找前k个数的topK问题
void TestHeap4()
{ //数据先假设为10000个int n = 10000;int k = 5;srand((size_t)time(0));//造数据FILE* fin = fopen("Data.txt", "w");if (fin == NULL){perror("fopen fail.\n");exit(-1);}for (int i = 0; i < n; ++i){int val = rand();fprintf(fin, "%d\n", val);}fclose(fin);//将前k个数建成一个小堆int minHeap[5];FILE* fout = fopen("Data.txt", "r");if (fout == NULL){perror("fopen fail.\n");exit(-1);}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//向下调整建小堆for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDown(minHeap, k, i);}//逐一遍历数据，找出最大的数int val = 0;while (fscanf(fout, "%d", &val) != EOF){if (val > minHeap[0]){minHeap[0] = val;AdjustDown(minHeap, k, 0);}}fclose(fout);for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}printf("\n");
}