【初阶数据结构】一文讲清楚 “堆” 和 “堆排序” -- 树和二叉树（二）（内含TOP-K问题）
文章目录
前言
在我们学习完树和二叉树的一些基本概念和性质之后，我只是简单的讲解了一下树的创建方式，我们还并未讲二叉树的一些应用。那么在本文中我就会讲二叉树的应用——“堆”，以及用对这个数据结构来实现堆数组进行排序的功能。这个就是大名鼎鼎的"堆排序"。
我还会针对堆排序给大家再次拓展一个大家在以后编程的道路上，会经常的遇到的一个实际问题：就是在一大堆数据中找出最大或最小的前几个数，这个问题的本质就是堆排序，我们也将这种问题，称为"TOP-K"问题。至于它是怎么实现的，请大家接着往下看！
1. 堆
1.1 堆的概念
我在这里不想给大家讲官方的定义，就直接给大家以一种更好理解的讲解。
堆，其实就是一棵完全二叉树。但是这棵完全二叉树得满足一些性质，
- 性质1：堆中某个结点的总是不大于或不小于其父节点的值；
- 性质2：堆总是一颗完全二叉树。(这个我们提到过了)
所以我们就记住以上两个性质，如果都符合了，那你就可以说这是"堆"。
由性质1就可以引出"堆"的两种类型。
1.2 堆的分类
堆分为两种：
- 大堆（大根堆）：首先它得是一棵完全二叉树，其次它的某一个节点都不大于其父节点(小于或等于其父节点)。这个就是大堆的玩法。
- 小堆（小根堆）：首先它得是一棵完全二叉树，其次它的某一个节点都不小于其父节点(大于或等于其父节点)。这个就是小堆的玩法。
还记得吗？完全二叉树可以使用顺序表来实现，这个是得益于完全二叉树的特性决定的。既然堆也是一棵完全二叉树，那么我们也就可以用类似于顺序表这种物理结构(顺序存储)来进行堆的实现。
在这里，先给大家一幅图，感受大堆和小堆在逻辑结构和物理结构的模样，帮助大家更好的理解堆这个数据结构:
2. 堆的实现
讲完堆的基本概念之后，我就要详细的给大家讲讲堆是怎样用代码实现的，内容很丰富，希望大家能够好好看！
2.1 堆的结构体设置
我们在之前讲过了，堆是一棵完全二叉树，我们可以用顺序表来实现。那我们就可以这样定义堆的结构体：
//对int进行起别名，是为方便代码的后期维护
typedef int HeapDataType;
typedef struct Heap
{
HeapDataType* a;
int size; //记录申请动态空间中有效的数据个数
int capacity; //记录空间大小
}Heap;
2.2 堆的初始化
我们在开始实现每一个数据结构的各接口操作之前，我们都得为这个数据结构进行初始化，这些都是一些老套路了。
void HeapInit(Heap* php)
{
assert(php); //传进来的指针不能是空指针，不要就会造成对空指针进行解引用的误操作
php->a = (HeapDataType*)malloc(sizeof(HeapDataType)*4);
php->size = 0;
php->capacity = 4; //因为我申请了4个HeapDataType类型大小的空间
}
2.3 堆的销毁
有动态内存申请，就必要要释放空间，我们不能总是让操作系统来帮我们擦屁股，我们得有意识的释放动态内存申请之后的空间，这对于我们提升代码的能力是一种很好的帮助。
void HeapDestory(Heap* php)
{
assert(php);
free(php->arr);
php->arr = NULL;//养成好习惯
php->size = 0;
php->capacity = 0;
}
2.4 添加数据到堆
这里我们只需要一个函数就行。
那这时有的读者就会提问了，为什么不写一个头插数据的函数和一个尾插数据的函数，而只需要写一个添加数据的函数即可？
原因就是，我们在之前反复提到，堆是一棵特别的完全二叉树。那我们往这个堆中添加数据，添加完数据之后，这个数据结构也还是堆啊。那既然是堆，就得满足堆的特性。 我们总不能把人家的东西给彻底玩坏了吧。
那不管是头插还是尾插，甚至是在某个位置上插入数据，在最后都得被调整到符合堆这个数据结构特点的位置上。这就会给我们一个感觉就是不论我在哪个位置上插入，跟我直接插入数据效果是一样的。为此我们直接洗一个插入数据的函数即可。
上面的解释中，提到了一个名词"调整"，那到底怎样调整呢？这个就是本文的核心所在，怎么解决调整数据的问题。
2.4.1 "向上调整"算法
在讲如何调整数据使之再次成为堆之前，我要给大家灌输一个思想，这个思想也是很多人在刚开始学习堆时，比较难以转换的。这个思想就是“看树不是树”。
什么意思呢？
堆在逻辑上是一棵完全二叉树，但是在物理结构上是顺序表。所以我们要想堆不过就是在内存中连续存储的数组罢了。
那基于这层思想，我们向堆里面插入数据，无非就是往数组中插入一个数据。插入完数据之后，再进行数字位置之间的调整，使这个数组再次成为堆。 这个就是本算法的核心思想。
那我们该如何调整数组中数字的位置，使之成为堆呢？
在开始讲之前，我会结合以下的这棵完全二叉树进行讲解（这里我拿大堆举例）
可以看到它物理结构时候的样子，那我们先插入一个数字看看改变之后的样子。
可以看到的一个规律就是，我即使添加了一个数据之后，仍有部分的子树仍然是遵循堆的玩法的。这就给我们提供了一个很重要的思考方向，就是从把"堆"弄的不像"堆"的的那棵子树入手。可以从上面的图中看出，“罪魁祸首”的那棵树在我们添加数据的那个节点直至它的祖先，形成的类似于"导线"的样子。
讲了这么多，就是让大家明白一个道理。为什么这个算法叫做"向上调整"？是由它的操作决定的。则会个算法通过将添加的数据的不断地往上调整，最终到达属于它的"皇位"之上。
那接下来，我就得聊一聊怎么挪动的了。这里针对的是大堆。
可以看到的是挪动之前，我们得先判断它是否需要挪动？挪动到什么位置就停止？
这个就必须要知道孩子节点与其父节点之间的值的大小关系了。
现在我告诉大家一个公式，这个公式十分重要，大家一定要理解性记忆！！！
假设孩子结点叫做
child，父亲节点叫做parent。(这里的 child 和 parent 的值是数组的下标)
parent = (child - 1) / 2
left_child = parent * 2 + 1
right_child = parent * 2 + 2
倘若我们真的掌握了这三条公式，我们就可以通过孩子结点的下标直接找到其父节点，我们也可以根据父节点找到其对应的孩子节点。这两者可以相互被访问！
ok，有了以上的思路，我们就开始写代码吧。
void HeapPush(Heap* php, HeapDataType x)
{
if(php->size == php->capacity)
{
HeapDataType* tmp = (HeapDataType*)realloc(php->a,sizeof(HeapDataType) * 2 * phph->capacity);
if(tmp == NULL)
{
perror("realloc fail");
return;
}
//成功扩容
php->a = tmp;
php->capacity *= 2;
}
php->a[size] = x;
php->size++;
//对插入的数据进行位置调整，使之再次成为大堆！得用到向上调整算法
AdjustUp(php->a,php->size);
}
void Swap(HeapDataType* x, HeapDataType* y)
{
HeapDataType tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整算法
void AdjustUp(HeapDataType* 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;
}
}
}
ok，我们代码就这样水灵灵的写出来了。那么我请大家思考一个问题，我把while循环的额条件变为parent>=0可以吗？
也许有的人会说，这个好像可以吧。但事实上，我不建议大家这么写。大家不妨思考一下，当parent变为0时，循环条件成立，进入循环执行循环体。当执行到
parent = (child - 1) / 2这条语句时，parent的值是0，为此它还会再一次进入循环。但不会出现死循环的情况，因为if条件已经不满足了。
为此这里还是建议大家写child>0这个判断条件。
2.5 从堆中删除数据
讲完了添加数据到堆的操作之后，肯定还要再讲它的孪生兄弟"从堆中删除数据"。
它的思想跟添加数据的思想大部分是一致的，这里我就不再讲多余的部分了。直接进入最核心的部分，我们该在哪个位置删除数据？删除完数据之后，父亲结点和孩子节点的大小关系肯定就会混乱了，那我们该怎么调整？
这些问题，在下面我都会给大家一一讲解！睁大眼睛，不要错过了哦！
首先我们先解决第一个问题，该删除数组上哪个位置上的数据？
有的不假思索的就会说，删除数组中最后一个位置上的数据！但是这样删除数据有意义吗？这个是我们要思考的问题。从逻辑角度上看，好像对整棵树没有什么影响啊。确实没有影响，删除这种位置上的数据是没有任何意义的！
既然要玩，我们就玩大的！删掉根节点。这就好比在一个黑帮中，老二觊觎老大的位置，狠不得找个机会做掉老大，总而自己主管整个黑帮。老三肯定也是想把老二做掉，让自己走上更高的位置。这个道理就类似于堆的删除操作背后的含义。
到这里，我们就理解了第一个问题，要删除数据就删除堆中的根节点。
接下来，我们就得解决第二个问题。那就是删除完数据之后，父亲结点和孩子节点的大小关系肯定就会混乱了，那我们该怎么调整？
这个问题就好比，有一天老二真的把老大给做掉了，但是老二肯定得收买黑帮成员里面的人心，支持他做老大。
下面我画一幅图，给大家来一个直观的感受。
这个时候，就要在给大家介绍另一个算法“向下调整”。
2.5.1 “向下调整”算法
事先说明一个重要的点，在使用这个算法之前，必须得确保根节点的左右子树都得是堆。
想要删除根节点的数据，我们可以将根节点数据与数组中最后一个位置上数字交换值，或则是直接覆盖。这里简单一点就直接将最后位置的值赋值给根节点，这就相当于将根节点进行删除了。
那下一步我们就得调整各数字的位置了。用得算法就是“向下调整”。
那该怎么向下调整呢？
首先我们知道了一个条件，根节点的左右子树还是一个堆。那我们只需要将根节点(父节点)与它的左右孩子节点的值作比较，如果比左右孩子结点值大的那个更小的话，那就交换它们的值。如果都比这两孩子结点都大的话，那就不用调整位置了。
根据以上的思路，我们就来写写代码。
void HeapPop(Heap* php)
{
assert(php && php->size != 0);
php -> size--;
//向下调整算法
Adjust(php->arr,php->size,0);
}
void AdjustDown(HeapDataType* a,int n,int parent)
{
//相比较左右孩子结点的值，选取其中最大的那个
//这里我使用假设法，先假设左孩子的值大于右孩子的值。这样就可以避免设置多余的变量
int child = parent * 2 + 1; //这个上面提到过的公式
while(child < n)
{
if(child + 1 < n && a[child] < a[child + 1])
{
child++;
}
//比较完左右孩子大小之后，就要跟父节点进行大小的比较了
if(a[parent] < a[child])
{
//说明得交换值了
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
到这里，向下调整的算法也将讲完了！希望大家能够好好的消化。
之后，一些堆的方法接口的就比较简单了，我就一次性给大家写代码即可。
2.6 堆的其它各种方法接口函数
//判断堆是否为空
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0 ? true : false;
}
//计算堆的大小
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
//查看堆的根节点的值
HeapDataType HeapTop(Heap* php)
{
assert(php && !HeapEmpty(php));
return php->a[0];
}
好了，到这里，我们就能完整的实现一个堆了。
那接下来，我们就来讲一下"堆排序"！
3. 堆排序
堆排序，顾名思义，就是利用堆这个数据结构对数据进行（升序/降序）排序。
回顾一下我们学过的数据结构，从顺序表到链表、栈、队列以及我们现在学的堆。堆这个数据结构有很强烈的现实意义，因为它能给我们的数据进行排序，而且效率是目前效率最高的（在没有学排序算法之前）。
那么我们如何用堆进行排序呢？我先给大家一个场景，先让大家去想！
void HeapSort(int* a,int n)
{
//怎么实现？
}
int main()
{
int a[] = {5,2,3,7,1,9,8,10,6,4};
//堆排序
HeapSort(a,10);
}
3.1 堆排序的代码实现
现在我来揭晓答案:
void HeapSort(int* a,int n)
{
//向上调整的时间复杂度为O(N*logN)
/*for(int i = 0; i < n; i++)
{
AdjustUp(a,i);
}*/
//向下调整的效率更高，时间复杂度为O(N)
for(int i = (n - 1 - 1) / 2; i >= 0 ; i--)
{
AdjustDown(a,n,i);
}
//这一步就是将最大的数字，置换到数组的尾部。最后再进行调整
for(int end = n - 1; end > 0 ; end--)
{
Swap(&a[end],&a[0]);
AdjustDown(a,end,0);
}
}
int main()
{
int a[] = {5,2,3,7,1,9,8,10,6,4};
//堆排序
HeapSort(a,10);
for(int i = 0 ; i < 10 ; i++)
{
printf("%d ",a[i]);
}
}
4. TOP-K问题
4.1 什么叫TOP-K
顾名思义，就是求前K个数值。可能是最大的前K个，也可能是最小的前K个。
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
4.2 TOP-K问题求解的思路
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
4.3 TOP-K问题的代码实现
这里我们就用文件操作生成10000个数字，每个数字的范围是在0~999之间。找出这10000个数字最大的前10个打印出来。
void CreatData()
{
srand((unsigned int)time(NULL));
FILE* fin = fopen("data.txt","w");
if(fin == NULL)
{
perror("fopen fail");
return;
}
for(int i = 1; i<=10000; i++)
{
fprintf(fin,"%d\n",rand()%1000);
}
fclose(fin);
fin = NULL;
}
void PrintTopK(const char* filename, int k)
{
FILE* fout = fopen(filename,"r");
if(fout == NULL)
{
perror("fopen fail");
return;
}
int* topk = (int*)malloc(sizeof(int) * k);
for(int i = 0; i < k; i++)
{
fscanf(fout,"%d",&topk[i]);
}
for(int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(topk,k,i); //这里如果是要选最大的话，调整为小根堆。反之，调整为大根堆。
}
int val = 0;
int ret = fscanf(fout,"%d",&val);
while(ret != EOF)
{
if(topk[0]<val)
{
topk[0] = val;
AdjustDown(topk,k,0);
}
ret = fscanf(fout,"%d",&val);
}
//最后打印结果
while(k)
{
printf("%d ",topk[k-1]);
k--;
}
fclose(fout);
fout = NULL;
free(a);
a = NULL;
}
大家为了方便测试，可以在data.txt这个文本文件中，将其中10个值改为都大于1000的，这样的话，测试的结果就显而易见了。
测试结果：
到这里关于堆的内容就已经全部讲完了！
如果觉得本文写还不错的话，麻烦给偶点个赞吧！！！
原文地址：https://blog.csdn.net/tianxiawushanu/article/details/142319389
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！