这篇博客我会尽我自己的所能讲解堆，同时详细的解释堆中重要的向下和向上调整算法，以及推排序的两种实现方法，和堆的TOPK问题。
堆是什么
我们之前已经介绍过了树，而堆就是一种完全二叉树。
这里我放一张二叉树的图
下面我来解释一下满二叉树，和完全二叉树的区别：
满二叉树是指除了叶子节点外，每个节点都有两个子节点，且所有叶子节点都在树的同一层次上。换句话说，满二叉树是一颗高度为h，且具有2^(h+1)-1个节点的二叉树。例如，下图所示的二叉树就是一颗满二叉树：
6
/ \
4 8
/ \ / \
2 5 7 9完全二叉树是指除了最后一层外，其他所有层都被完全填充，最后一层可以有从左到右缺少一些节点，但这些节点只能出现在最后一层上，且不允许有空洞。换句话说，完全二叉树是一颗高度为h，具有2^h 至 2^(h+1)-1 个节点的二叉树，其中最后一层的节点都在最左边，不会出现在右边。举个例子，下图是一颗完全二叉树：
6
/ \
4 8
/ \ /
2 5 7在完全二叉树中，可以用数组来存储节点，存储顺序为从上到下、从左到右的顺序。这样，可以用较少的存储空间存储一颗完全二叉树。
需要注意的是，满二叉树是一种特殊的完全二叉树，而完全二叉树不一定是满二叉树。
堆父节点和子节点的关系
如果父节点的下标为i，那么左孩子节点的下标也就是2*i+1，右孩子节点就是2*i+2
而堆也有两种一种是大堆
大堆和小堆的区别
（大堆）根节点的值是整个堆中的最大值。因此，从堆中取出根节点元素时，可以得到堆中的最大值，这是大堆的一大优点。
（小堆）根节点的值是整个堆中的最小值。因此，从堆中取出根节点元素时，可以得到堆中的最小值，这是小堆的一大优点。
下面我们就来看一下要实现一个堆要实现的函数。
我这里先写一个大堆
堆要实现的函数
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//用以储存数据
int size;//数据的个数
int capacity;//能储存多少数据
}Heap;
//我这里实现的是大堆
// 堆的构建
void HeapCreate(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);堆函数一：初始化
这个函数很简单。
void HeapCreate(Heap* hp)//也即将结构体给初始化
{
assert(hp);
hp->a = NULL;
hp->size = 0;
hp->capacity = 0;
}堆函数二：插入数据
插入数据本身是很简单的，因为我要完成的这个堆虽然逻辑结构是一个堆，但是物理结构仍然是一个数组。但是我们只插入数据不行我们还要调整插入数据的位置让其满足一个大堆/小堆的特点。
而调整数据也是有两种方法的，一种是向上调整，一种是向下调整。
我先写出插入数据完整的代码
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//判断是否需要扩容
if (hp->size == hp->capacity)
{
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
hp->size++;//完成插入
//但这是显然不够的我们还需要向上调整使其满足一个大堆或是一个小堆的条件
AdjustUp(hp->a, hp->size-1);//这里是向上调整，下面我会解释
}下面我来详细解释一下向上调整和向下调整函数。这也是最重要的函数。
向上调整算法（重要）
我们先使用画图来解释一下这个调整的方法是什么？假设我们要建立一个大堆，现在堆中已经有了7个元素，下面的就是物理结构
逻辑结构：
现在我们要再次插入一个元素是10，如果不做任何的调整逻辑结构就就会变成下面这样：
这很明显不符合大堆的特点所以这里我们就要从10开始，往上先找到10的父节点也就是2，比较谁大，子节点大则交换让2和10换位，继续往上判断直到那一次父节点大于了字节点或是到达堆顶时停止。
经过这样的调整之后逻辑结构也就会变成下图：
概括的说这个函数也就是通过子节点找到父节点（i-1）/2也就是父节点的下标（i为子节点下标）。然后比较父节点和子节点的大小判断是否需要交换，（这里分情况）大堆：子节点大于父节点则要交换，直到父节点大于子节点或是直到没有父节点（父节点的下标越界了）存在了。小堆：子节点小于父节点则要进行交换，直到父节点小于子节点，或是没有父节点（父节点的下标越界了）存在了。
下面我们就来实现这个算法
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;//如果父节点大于此时插入的新节点不用继续调整，直接break即可，因为我这里做的是大堆，所以如果这里父节点大于了
//子节点
}
}
}还要注意的一点是对于向上调整算法，我们必须保证所要修改的节点的上面已经是一个大堆或是小堆了，否则这种算法是会出错的。
堆函数三：删除数据
删除数据方法1：左移
首先要知道对于堆中的数据而言，如果我们删除堆底的数据是没有任何意义的，所以对于堆而言删除数据删除的是堆顶的数据。那么我知道堆的物理结构是一个数组对于数组而言删除堆顶的数据我们可以采用移动的方法，但是这种方法对于对而言真的好吗？我们通过图来表述
就以这个大堆来做解释：
下面是未删除8的逻辑结构：
下面是删除8之后的逻辑结构：
仅从4和5这两个数据上我们就能看到很大的差别，拿一句话来说也就是5我4拿你当兄弟，但你却想当我的父亲，可以看到逻辑结构完全变化了，这是不正确的。也许你会认为这样不行吗？因为我上面的图虽然让逻辑结构发生了变化但是这依旧是一个大堆啊，这符合条件啊。但这我确实只能说这仅仅只是一个巧合。如果是下面的这个数据组呢？
逻辑结构：
如果是使用移动的方法删除10之后呢？逻辑结构就变成了下面这样
很显然这已经不是一个堆了。所以如果你要使用左移来删除堆顶的数据的话，在删除之后我们要重新建立堆，这是很麻烦的，所以我们这里使用方法二
删除数据方法二：交换后删除
这里我可以先让堆顶的数据和堆底的数据先进行交换交换完之后我在使用向下调整算法（下面会解释）也就完成了堆数据的删除。
下面是实现代码：
// 堆的删除（删除的是堆顶的元素）
void HeapPop(Heap* hp)
{
//堆的删除有两种方法，方法1：你可以使用移动删除法，但是删除之后堆内的父子关系就被彻底打乱了
//我们需要重新建立堆
//方法二：我们将堆顶的元素和最后的元素调换之后删除最后的元素之后向下调整
assert(hp);
assert(!HeapEmpty(hp));
swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
//AdjustUp(hp->a, hp->size - 1);//这里使用向上调整是行不通的，因为向上调整我们所选取的只是一个孩子节点，有可能另外一个孩子节点也可能大于右节点
AdjustDown(hp->a, hp->size, 0);
//这样就不能构成一个堆了，所以这里我们使用向下调整的方法去完成堆的删除
}下面我来解释向下调整算法
向下调整算法（重要）
首先我们知道向上调整算法是通过孩子节点找到父节点，然后比较再进行交换，而向下调整算法则是我们传过去的是父节点的下标，通过父节点找到子节点，再比较父节点和子节点是否需要交换，和向上调整算法一样，向下调整算法也需要保证所调节节点下方的数据已经是一个堆了。
下面我来图解一下向下调整算法
就拿下面的例子来解释：
这是物理结构
这是逻辑结构：
我们让10和1的位置互换然后删除10的位置，我们的逻辑结构也就变成了下面这样：
需要注意通过父节点找到字节点的过程中，如果你是大堆那么你要找的肯定是两个子节点中大的那个进行比较，如果是小堆肯定是要和小的那个进行比较。那么这里我在这里不推荐使用if else来写那样写会造成逻辑的重复。我这里推荐使用假设法，我们先假设左节点是目标节点将其赋给一个变量，我们再拿这个变量和右节点比较如果右节点更符合条件则修改变量值，这样我们也能找到目标节点。
继续上面的这个图，将1和8比较很明显8更大则交换1和8。再比较1和4很明显4更大再次交换，当1来到最顶层之后没有孩子节点了算法结束。从这里我们也能知道和向上调整算法一样向下调整算法的结束条件也有两个一个是，交换中途满足了条件算法结束，另外一种也就是调整到了没有字节点的位置算法依旧也是结束。
经过向下调整之后上面的逻辑结构就会变成下面这样：
下面我们来完成代码：
void AdjustDown(HPDataType* a,int n, int parent)//这里的n就是元素个数
{
int child = 2 * parent + 1;//我这里假设child就是最大的数
while (child < n)//因为我们是通过父节点去寻找子节点的，所以当求得到的子节点大于元素个数时，代表parent来到了
//最底部的节点不能再交换，否则会越界访问
{
if (child+1<n&&a[child] < a[child + 1])//如果右孩子大于左孩子就改变child,如果没有右孩子则不需要判断,
//这里要需要考虑如果改父节点如果只有1个子节点的情况。
//如果你要建立小堆只用改变为小于号即可
{
child++;
}
if (a[parent] < a[child])
//建立小堆这里也要改变为小于号
{
swap(&a[parent], &a[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;//如果父亲大于最大的孩子则满足大堆条件
}
}
}堆函数四：获取堆顶的元素
这里我们要知道物理结构仍然是一个数组，而数组的头元素自然是下标为0的数字。
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));//判断是否为空
return hp->a[0];//a[0]就是栈顶元素
}堆函数五： 堆的数据个数
// 堆的数据个数
int HeapSize(Heap* hp)
{
return hp->size;
}堆函数6：堆的销毁
void HeapDestory(Heap* hp)
{
free(hp->a);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}堆函数七：判断堆是否为空
// 堆的判空
bool HeapEmpty(Heap* hp)
{
return hp->size == 0;
}堆的应用：堆排序
推排序的实现方法一
现在给你一个数组我们怎样将它排序成有序呢？这里假设我们是要将数组排序成降序的。那么我首先就会将数组里面的所有数据都建立成一个大堆，然后先获取堆顶地元素将其放入原数组中，再删除堆顶的元素。不断地删除知道堆中没有数据也就完成了数组地排序。在写代码之前我们先来考虑一下这种写法的缺点。
缺点
- 我们要使用这种方法那么你首先就要完成一个能够增删查改的堆也就是至少要完成堆函数的初始化，插入，删除，获取堆顶函数。
- 这种方法的空间利用率很低，而且需要我们拷贝数据
我们待会使用的方法二就能很好的解决这两个问题，下面我先将这个代码完成。
// 对数组进行堆排序
void HeapSort(int* a, int n)
{
Heap hp;
HeapCreate(&hp);
for (int i = 0; i < n; i++)
{
HeapPush(&hp,a[i]);//将数组里面的数字全部储存进堆里面
}
int i = 0;
while (!HeapEmpty(&hp))
{
int val = HeapTop(&hp);
a[i++] = val;
HeapPop(&hp);
}
HeapDestory(&hp);//使用这种堆排序的话你建立大堆最后出现的就是降序，而小堆就是升序
//这种方法可行但是需要我们1先写一个完整的堆，并且这样的写法空间复杂度很高,而且需要我们拷贝数据
}堆排序的实现方法二
那么我们能否就将原数组先建立成一个堆呢？这肯定是可以的，在我们将原数组建立成一个堆之后（假设是大堆），我们又要如何完成排序呢？我们可以在完成堆之后使用和删除函数差不多的思路，将堆顶的最大元素和堆底的元素交换，之后我们在使用向下调整算法的时候，不将最后的元素包含起来，再将次大的元素找出来，放到堆顶后交换放到原数组倒数第二的位置，再次向下排序，这样我们也就能知道建立大堆最后得到的就是一个升序的数组。
下面我通过画图来解释上面的这个过程。
下面的这个就是无序的一个数组。
我们将其建立成一个大堆之后的物理结构和逻辑结构如下图：
现在我们交换9和4然后再从堆顶开始重新向下调整（不包括9的位置），然后我们再来看新的逻辑和物理结构：
再然后我们继续将8和1交换之后再向下调整的时候将8和9的位置都不包含的情况下再次建立大堆，这样直到最后我们就能够得到一个升序的有序数组。
下面我们来重点讲解堆排序中如何建立一个大堆/小堆
堆排序中建立堆的方法
首先在堆排序中要建立一个堆就要使用向下调整算法和向上调整算法，由此建立堆也就有了两种方法一种是使用向上调整的算法建立堆，一种是使用向下调整的方法建立堆。这两种算法的时间复杂度的计算我会在下一篇博客中指出。
向上调整建堆
要记住使用向上调整算法，传过去的是孩子节点，算出来的是父节点。
我在向上调整算法的那一节说过，我们在对一个节点使用向上调整算法的时候，我们必须保证在这个节点上面的节点已经是一个大堆/小堆了。如果我们从最后的节点开始向上调整的话肯定是不行的，很明显在最后的节点前面的节点不是一个堆。所以我们这里要从第二个数据开始向上调整，因为单个数据默认就是一个堆，那么在调整完两个数字后，我们在从第三个数子开始往上调整，直到我们将所有的数字调整完成，最后我们就能够得到一个大堆或是小堆。
下面是代码：
for (int i = 1; i < n; i++)
{
AdjustUp(a,i);
}//通过向上调整我们就能将数组a调整为一个大堆向下调整建堆
向下调整算法，传过去的是父节点，得出的是子节点
和向上调整算法一样，在对一个节点使用向下调整算法的时候，必须保证这个节点下方的节点们必须是大堆或是小堆。要知道单个节点默认是堆所以我们要找到第一个非叶子节点，即最后一个父节点，然后调整这个父节点下方的子节点，然后减去1找到倒数第二个父节点不断的向上，直到最后调整根节点。就完成了建立堆
下面是代码：
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1代表的是最后一个元素的下标再次-1除以2
//是找到这个元素的父节点，也就是最后一个父节点
{
AdjustDown(a, n, i);
}下面我们来完善推排序的代码：
void HeapSort(int* a, int n)
{
// 对数组进行堆排序
//要使用堆排序我们首先就要建立堆，建立堆有两种方法，其中一种是向上建立堆，一种是向下建立堆，同时排序也有两种排序方式，
//其中一种是升序排列，一种是降序排列
//这里我们需要知道如果你要升序排列那么你要建立大堆
//而如果你要降序排列那么你就要创建小堆
//至于这是为什么，堆排序的思路也就是我们让堆顶的元素和堆底的元素交换（如果这是大堆那么堆顶的元素就是最大的元素），然后将最后一个元素删除，让上面的元素全部重新调整
//再次取出次大的元素放到倒数第二个元素，那么到最后我们就会得到一个升序的数列
//首先是创建一个堆有两种建立方式一种是向上建立堆的方法，一种是向下建立堆的方式这里和上一种方法最不同的一点就是我们直接将待排序的数组建立成堆
//然后有两种方法建立堆
//向上调整建堆和向下调整建堆
//首先就是向上调整建立堆,这里建立堆使用的是原数组即我们不再重新创建一个堆而是将数组建立成堆
for (int i = 1; i < n; i++)
{
AdjustUp(a,i);
}//通过向上调整我们就能将数组a调整为一个大堆
//因为做成的是大堆所以最后排序的时候出来的是一个升序
//现在开始使用向下调整建立大堆
//向上调整要满足的条件就是左右子树必须是一个大堆
//所以我们从堆的最顶层开始向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1代表的是最后一个元素的下标再次-1除以2是找到这个元素的父节点
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[0], &a[end]);//交换头尾两个元素
AdjustDown(a, end, 0);//向下调整重新建立堆，这里的end指的是元素个数，因为我们删除了第n-1个元素，但是第n-1个元素
//之前的元素个数本来就是n-1
end--;//最后让end--将最后一个元素删除让其不再进入调整
}
}这里我详细解释一下这一段
while (end > 0)
{
swap(&a[0], &a[end]);//交换头尾两个元素，这里我是写了一个简单的交换两个数的函数
AdjustDown(a, end, 0);//向下调整重新建立堆，这里的end指的是元素个数，因为我们删除了第n-1个元素，但是第n-1个元素
//之前的元素个数本来就是n-1
end--;//最后让end--将最后一个元素删除让其不再进入调整
}我们要知道在AdjustDown(a, end, 0)；这里面的end代表的是要向下调整的数目，而在while里面end代表的是下标，这里我们要知道最后一个元素的下标等于前面元素的个数，例如一个数组 1 2 3 4。4的下标是3，而3恰好就是前面元素的个数。那么这里也是一样的，我们现在需要调整的是最后一个元素前面的所有元素，所以我们这里将end传过去代表的是要调整的元素个数。最后我们让end--等于交换倒数第二个元素，再调整倒数第二个元素前面的所有元素。
堆的TOPK问题
首先什么是堆的topk问题呢？堆的topk问题也就是从n个元素里面选出前k个最大的/最小的数（n<k）。
解决这个问题有好几种方法，我这里提出两种其中一种就是我们将n个元素全部建立成堆，然后获取不断获取头部元素再删除，这是其中一种方法。
方法一 缺点：如果n非常大呢，例如这个n为10亿，然后要你选出前5个最大的。
这个缺点会出现的原因就是在内存里面很难创建10亿个数据，因为10亿个整型数据要占据的内存空间大概也就是3.75GB，这个对于内存而言也是很大的。因为我们计算机还要考虑到系统运行的内存消耗。所以这么多的数据我们就要将其储存进硬盘里面。
方法二：
首先我们要将所有的n个数据放进硬盘里面，然后我们读取前面的k个数据将这k个数据建立成小堆（因为我们要寻找最大的k个数）。然后我们在一个一个的读取硬盘里面的数据，将数据和堆顶的数据比较，如果大于堆顶的元素那么就将其放入堆顶，在对堆进行一次向下调整。
下面我们来看代码：
void CreateNDate()
{
// 造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = rand() % 1000000;//模了一个100万也就让我们创造的数据大小都小于100万
//那么在最后验证的时候我们就可以在已经创建的文件
//里面修改k个数据，判断最后打印的是否是你修改的数据
fprintf(fin, "%d\n", x);
}
fclose(fin);
}//这上面的代码是用于造数据的
void PrintTopK(int k)
{
const char* file = "data.txt";
FILE* fin = fopen(file, "r");
if (fin == NULL)
{
perror("fopen error");
return;
}
int* a = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++)
{
fscanf(fin, "%d", &a[i]);//将文件开头的前k个元素读入到我们创建的数组里面
}
//读取完毕之后我们就要开始建立堆了，建立大堆最后得到的就是10个最小的元素，建立小堆最后得到的就是10个最大的元素
//这里我们建立的就是大堆
//使用向下调整的方法
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, k, i);
}//这样我们就建立了一个小堆
//现在完成最后的一步将剩余的元素和堆顶的元素比较如果大于堆顶的元素就进入堆中
int val = 0;
while (!feof(fin))
{
fscanf(fin, "%d", &val);
if (val > a[0])//如果读取的这个元素大于了堆顶的元素证明这个元素可能是最大的10个元素进堆中
{
a[0] = val;
AdjustDown(a, k, 0);//进入堆后向下调整一次
}
}
fclose(fin);
for (int i = 0; i < k; i++)
{
printf("%d\n", a[i]);
}
free(a);
a = NULL;
}
int main()
{
//堆的topk问题也就是给你10000个元素从中得到前10个大元素或是小元素
//方法1：我们将这些元素全部建立成堆然后toppop九次即可。
//但是这种解法在面对元素极其多的时候会出现问题也就是空间会不足，所以这里我们使用方法二
//我们直接选择用前10个元素建立成一个堆然后我们遍历整个元素，这里如果我们这里建立的是大堆那么最后找到的就是
//最小的10个数，如果建立的是小堆最后建立的就是10个最大的数
//CreateNDate();//创造数据，因为这里我已经创建了一次所以这里就将其注释了
PrintTopK(10);//从中寻找前10个元素
}下面就是运行图像：
到这里，我就基本介绍完了，希望这篇博客能对你有帮助。如果有错误请提出我一定改正。
标签：int,hp,元素,堆排序,大堆,TOPK,解决,节点,调整 From： https://blog.51cto.com/u_15838996/6327521