堆排序以及TOP-K问题

片头

嗨！小伙伴们，大家好！今天我们来深入理解堆这种数据结构，分析一下堆排序以及TOP-K问题，准备好了吗？我要开始咯！

一、堆排序

这里我们先假设要排成升序，也就是从左到右，结点的值依次增大

思路一：①先有堆这个数据结构，②给定一个数组arr, 我们可以把arr数组里面的元素全部拷贝到堆中，然后利用堆自身向下调整算法来进行排序，排成小堆，排好序后，再逐一拷贝回arr数组。

向下调整算法有一个前提：左右子树必须是堆

采用向下调整算法，从第一个结点(下标为0)开始，逐个进行比较，如果子节点比父节点大，则交换

第一次：

第二次：

第三次：

好啦，了解完向下调整算法后，那什么是向下调整建堆呢？

举个例子，接下来的内容可要仔细听好咯~

假设我们需要建立大堆，我们可以保持最后一层不动，也就是叶子结点的那一层不变，调整它的上一层，也就是从倒数第一个叶子结点的父节点开始向下调整，比较父节点的左孩子和右孩子，如果孩子结点比父节点大，那么交换，然后比较下一个父节点和它的孩子结点。

第一次：最后一个节点的下标为size-1,那么它的父节点(倒数第一个非叶子结点)的下标为(size-1-1)/2 ，比较父节点的左孩子和右孩子

第二次：从倒数第一个非叶子结点依次往前找父节点，也就是 (size-1-1)/2 -1 ，然后比较它的左孩子和右孩子

此时我们比较“70”的左孩子“50”和右孩子“32”，发现左右孩子都比父节点的值小，因此我们不作处理，继续往前寻找父节点。

第三次：往前找父节点，也就是 (size-1-1)/2 -1 -1，我们找到了“60”这个父节点，这里有一个隐藏的细节，不知道大家发现了没：“60”这个结点的左右子树都是大堆，这时，比较它的左孩子“70”和右孩子“100”，发现右孩子"100"比左孩子大，因此将父节点的值和子节点交换。

第四次：我们寻找“60”这个父节点的孩子结点，发现它只有左孩子结点，并且左孩子结点的值比父节点大，因此交换

OK啦，我们向下调整建堆就完成啦！

代码如下：

//交换
void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}//向下调整算法（小堆）
void AdjustDown(ElemType* arr, int size, int parent) {assert(arr);int child = parent * 2 + 1;//假设左孩子比右孩子小while (child < size) {		//还没有遍历到叶子结点的时候，进入循环if (child + 1 < size && arr[child + 1] < arr[child]){	//如果右孩子存在，并且右孩子的值小于左孩子child = child + 1;}if (arr[child] < arr[parent]){	//如果子节点小于父节点，交换Swap(&arr[parent], &arr[child]);parent = child;//将子节点赋给父节点child = parent * 2 + 1;//寻找下一个子节点}else{	//如果父节点小于子节点，退出循环break;}}
}//堆的构建
void HeapCreate(Heap* hp, ElemType* a, int n) {//断言，防止传入空指针assert(hp);//断言，防止传入空指针assert(a);//将堆的动态数组arr开辟一个能存放n个元素的空间hp->arr = malloc(n * sizeof(ElemType));if (hp->arr == NULL) {	//如果内存不足，开辟失败perror("malloc fail!\n");exit(1);}//将a数组里面的所有元素拷贝到堆的动态数组中memcpy(hp->arr, a, n * sizeof(ElemType));//堆的容量为nhp->capacity = n;//堆的大小为nhp->size = n;//向上调整建堆//从下标为1的元素开始，一直到下标为size-1的元素结束/*for (int i = 1; i < hp->size; i++) {AdjustUp(hp->arr, i);}*///向下调整建堆，将堆里面的所有元素调整成小堆//从最后一个结点的父节点开始，一直到根节点结束for (int i = (hp->size-1-1)/2 ; i >= 0; i--) {AdjustDown(hp->arr, hp->size, i);}
}//堆的判空
int HeapEmpty(Heap* hp) {assert(hp);//断言，防止传入空指针return hp->size == 0;//判断堆的大小是否为0
}//取堆顶的数据
ElemType HeapTop(Heap* hp) {assert(hp);//断言，防止传入空指针return hp->arr[0];//获取堆顶元素
}//堆的删除
void HeapPop(Heap* hp) {assert(hp);//断言，防止传入空指针Swap(&hp->arr[0], &hp->arr[hp->size - 1]);//将堆顶元素和最后一个元素进行交换hp->size--;//堆的大小减一AdjustDown(hp->arr, hp->size, 0);//向下调整算法
}//堆的销毁
void HeapDestroy(Heap* hp) {assert(hp);//断言，防止传入空指针if (hp->arr) {	//如果堆的动态数组存在，那么就释放占用的内存空间free(hp->arr);hp->arr = NULL;//置空}hp->capacity = 0;//堆的容量为0hp->size = 0;//堆的大小为0
}// 对数组进行堆排序
void HeapSort(int* a, int n) {assert(a);//断言，防止传入空指针Heap hp;//创建堆这个结构体HeapCreate(&hp, a, n);//堆的创建，将数组的元素全部拷贝到堆中，进行堆排序int i = 0;//数组下标从0开始while (!HeapEmpty(&hp)) {	//将堆里面的数据依次拷贝到数组中a[i++] = HeapTop(&hp);HeapPop(&hp);//每拷贝完一次，堆就删除堆顶元素}HeapDestroy(&hp);//堆的销毁，防止内存泄漏
}

测试一下：

#include"Heap.h"
int main() {int arr[] = { 23,45,89,12,33,78,100 };HeapSort(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {printf("%d ", arr[i]);}return 0;
}

运行结果为：

23 45 12 33 78 89 100

思路一理解起来很简单，但是它有2个致命的缺陷：①必须要提供堆这种数据结构！②空间复杂度为O(N) , 那还有没有其他方法呢？

思路二：①直接对数组进行向下调整建堆，先排成大堆 ②再采用交换思想，逐步排成小堆

不过，有一个小问题：我想排成升序，为啥不能直接建小堆呢？

来，咱们举个例子~

我们现在需要获取次小的元素，于是我们把栈顶元素删除

因此，如果要排成升序，只能选择建大堆！

还是arr数组，我们再来画一遍图~ 这次是建大堆，别忘记哈！

我们想要排成升序，该怎么做呢？

很简单~ 我们现在已知最大的元素是“9”，是堆顶元素，下标为0；最小的元素是“0”，是堆底元素，下标为 n-1 （n代表数组arr的个数），我们已知最大元素和最小元素，那么就让它们交换，将最大的元素放在最后

接下来把最后一个数不看作堆里面，也就是说堆里面原本有n个数，现在把最后一个数“9”不看作堆里面，现在一共有n-1个数。然后我们再开始从根节点向下调整，继续调整成大堆。（因为之前已经创建好大堆了，因此不需要从倒数第一个非叶子结点开始向下调整）

第一次：从下标为0的元素开始，比较它的左孩子和右孩子，如果其中一个子节点大于父节点，就进行交换。

第二次：继续比较父节点和它的子节点，如果其中一个子节点大于父节点，就进行交换。

第三次：继续比较父节点和它的子节点，如果其中一个子节点大于父节点，就进行交换。

完整过程如下：

OK,现在我们将剩余的元素又排成了大根堆，我们继续将堆顶元素“8”和堆底元素“4”进行交换~

第一次：

第二次：

第三次：

OK,此时已经符合大根堆，也就是堆中每一个父节点都大于子节点，左右子树都是大堆。

完整过程如下：

OK,现在我们将剩余的元素又排成了大根堆，我们继续将堆顶元素“7”和堆底元素“0”进行交换~

后面的过程和前面一样，这里就不画图了~

代码如下：

//交换
void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}//向下调整算法（大堆）
void AdjustDown(ElemType* arr, int size, int parent) {assert(arr);int child = parent * 2 + 1;//假设左孩子比右孩子大while (child < size) {		//还没有遍历到叶子结点的时候，进入循环if (child + 1 < size && arr[child + 1] > arr[child]){	//如果右孩子存在，并且右孩子的值大于左孩子child = child + 1;}if (arr[child] > arr[parent]){	//如果子节点大于父节点，交换Swap(&arr[parent], &arr[child]);parent = child;//将子节点赋给父节点child = parent * 2 + 1;//寻找下一个子节点}else{	//如果父节点大于子节点，退出循环break;}}
}//堆排序
void HeapSort1(int* a, int n) {assert(a);//断言，防止传入空指针for (int i = (n - 1 - 1) / 2; i >= 0; i--) {	//从最后一个结点的父节点开始，一直到根节点结束AdjustDown(a, n, i);//向下调整算法，调整成大堆}//这里的n-1有2层含义： //①数组最后一个元素的下标为n-1//②数组总共有n个数，交换后将最后一个值不看作堆里面，共n-1个数int end = n - 1;while (end > 0) {Swap(&a[0], &a[end]);//将首尾元素交换AdjustDown(a, end, 0);//向下调整算法，从下标为0的元素开始end--;//每交换完一次，都要把最后一个数不看作堆里面}
}

好啦，堆排序的两种方法讲解完毕，接下来我们继续学习TOP-K问题

二、TOP-K问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：几十个，几百个，几千个甚至是上亿个数字中找到最大的前K个数字。

对于TOP-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了（甚至无法将数据放入数组）。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前k个来建堆

*要找最大的前k个元素，建小堆

*要找最小的前k个元素，建大堆

2. 用剩余的N - K个元素依次与栈顶元素来比较，如果比堆顶的值大，就替换它进堆，堆整体向下调整

将剩余N-K个元素依次与堆顶元素比较完毕后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素，本次topk示例中计算的是最大的前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 (int i = 0; i < n; i++) {int x = (rand() + i) % 1000000;//产生随机数fprintf(fin, "%d\n", x);//将产生的随机数填充到文件中}//关闭文件fclose(fin);
}

这里将造出来的数据写入到data.txt文件中，运行完此函数后，当前目录下会多一个data.txt文件

打开此文本文件：

通过这个函数，我们已经成功造出了10000个数据了。

接下来就是topk代码的实现：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>//交换
void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}//向下调整算法(建小堆）
void AdjustDown(ElemType* arr, int size, int parent) {assert(arr);int child = parent * 2 + 1;//假设左孩子比右孩子小while (child < size) {		//还没有遍历到叶子结点的时候，进入循环if (child + 1 < size && arr[child + 1] < arr[child]){	//如果右孩子存在，并且右孩子的值小于左孩子child = child + 1;}if (arr[child] < arr[parent]){	//如果子节点小于父节点，交换Swap(&arr[parent], &arr[child]);parent = child;//将子节点赋给父节点child = parent * 2 + 1;//寻找下一个子节点}else{	//如果父节点小于子节点，退出循环break;}}
}//文件中找TopK问题
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;fprintf(fin, "%d\n", x);}//关闭文件fclose(fin);
}void PrintTopK() {        //这里的k是选出最大的前k个数printf("请输入k :>");int k = 0;scanf("%d", &k);//打开需要查找前K个数据的文件----data.txtconst char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL) {perror("fopen error");return -1;}int* minheap = malloc(sizeof(int) * k);//创建存放堆数据的空间if (minheap == NULL) //如果空间不足，则开辟失败{perror("malloc fail!\n");return -1;}for (int i = 0; i < k; i++) //往堆里面填充k个数据{fscanf(fout,"%d", &minheap[i]);}//建k个数据的小堆(倒数第一个非叶子结点开始向下调整)for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(minheap, k, i);}//将剩余n-k个元素依次与堆顶元素比较，如果比堆顶的值大，就替换它进堆int x = 0;while (fscanf(fout, "%d", &x) != EOF) {        //EOF是文件的结束标志，它的值是-1if (x > minheap[0]) {minheap[0] = x;AdjustDown(minheap, k, 0);//从第一个结点开始向下调整}}//打印前K个最大的数字for (int i = 0; i < k; i++) {printf("%d ", minheap[i]);}fclose(fout);fout = NULL;
}int main(){//CreateNDate();PrintTopk();return 0;
}