【初阶数据结构】一文讲清楚 “堆” 和 “堆排序” -- 树和二叉树（二）（内含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问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2. 用剩余的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的，这样的话，测试的结果就显而易见了。

测试结果：

到这里关于堆的内容就已经全部讲完了！

如果觉得本文写还不错的话，麻烦给偶点个赞吧！！！