【堆的应用--C语言版】

前面一节我们都已将堆的结构（顺序存储）已经实现，对树的相关概念以及知识做了一定的了解。其中我们在实现删除操作和插入操作的时候，我们还同时实现了建大堆（小堆）的向上（下）调整算法。

在这里我们需要补充：

       我们上一节实现的算法中的向上调整算法的时间复杂度为O(n*log n),而向下调整算的时间复杂度为O(n)。所以我们就可以知道，在建堆的时候尽量选择时间复杂度较小的向下调整算法。

一.堆排序

小Tip：排升序，建大堆；排升序，建小堆。

1.版本一：

基于已有数组进行建堆，取堆顶元素完成排序。

注：该版本有一个前提，必须提供现有的数据结构堆。

//1.需要堆的数据结构
//2.空间复杂度 O（N）
void HeapSort(int* a, int n)
{HP hp;  //创建一个堆for (int i = 0; i < n; i++){HPPush(&hp, a[i]);  //将数组中每一个元素逐个插入堆中}//逐个取堆顶的元素int i = 0;while (!HPEmpty(&hp)){a[i++] = HPTop(&hp);//取堆顶的元素HPPop(&hp);//出堆}//销毁堆HPDestroy(&hp);
}

 基于前面我们已经实现过堆的顺序存储结构，在这里我们就只实现局部代码。实现思路我在代码的旁边已经进行了标注。

2.版本二：

数组进行建堆，首尾交换，交换之后的堆尾从堆中删除掉，将堆顶数据向下调整选出次大的数据。

void HeapSort(int* a, i int n)
{//先进行向下调整算法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//循环 将堆顶数据进行交换，交换完将调整堆（堆中的要访问的底层数组的下标减1，在进行堆的调整的时候end还是 要调整的 堆中的元素个数）int end = end - 1;while (end){Swap(&a[0], &a[end]);AdustDwon(a, 0, end);end--;}
}

实现思路已经在上面的代码中已经标注了。

二 .top-k问题

          如果我们要在10个数据中，找前面3个最大的数据是多少，咋找？ 如果我们要在100个数据中，找前面3个最大的数据是多少，咋找？ 如果我们要在1000个数据中，找前面3个最大的数据是多少咋找？ ……如果我们要在100000000000000000个数据中，找前面3个最大的数据是多少，咋找呢？

        对于数据量少的，我们可以用前面所学的打擂台，冒泡排序，选择法排序，快速排序以及上面所讲的堆排序。但是对于数据量特别大的呢，我们如果还用上面所说的方法，那就太慢太麻烦了。现在我们所玩的游戏（有很多玩家）中找积分最多的前几个玩家？世界人口中找年龄最大的人？……用上面的方法是不是就很繁琐了。

        所以对于这种类似的问题结合堆的性质我们就Top-k来进行排序。Top-k问题：即就是求数据集合中前k个最大或者最小的元素，一般情况下数据量都比较大。

#include <stdio.h>
#include <stdlib.h>
void Swap(int* x, int * y)
{int temp = *x;*x = *y;*y = temp;
}//可不用，见后面
void AdjustDown(int* arr, int parent, int size)
{int child = parent * 2 + 1;//左孩子while (child < size)   //注意这里的条件{//找左右孩子中值最小的  小堆用>  大堆用<if (child + 1 < size && arr[child] > arr[child + 1]){child++;}//小堆用<  大堆用>if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//top-K 问题   求最大
void topk()
{int k = 0;printf("请你输入K>:");scanf("%d", &k);//以只读的方式打开文件const char *file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!");exit(1);}//用动态内存内存的知识，申请k个整形单位的数组int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//从文件中读取数据for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//取随机生成前k个数字进行建堆  利用向下调整算法进行建堆for (int  i = (k-1-1)/2; i >= 0; i--){AdjustDown(minHeap, i, k);   //建小堆}//将文件中剩余的数字和堆中的k个数据进行逐个比较，大的数字王进走，小的数字往出走int x = 0;while (fscanf(fout, "%d", &x)!=EOF){//如果此时读取到的数据大于堆顶数据，就将if (x > minHeap[0]){minHeap[0] = x;   //此处也可以用Swap函数进行数据的交换AdjustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);
}//先生成随机数字放在文件中
void CreatData()
{int n = 100000;srand((unsigned int)time(NULL));//利用时间戳进行堆随机数种子进行改变//以写的形式创建文件const char *file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fin fail!");return;}//向文件中写入用fprintf，向文件中写入数字for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
int main()
{CreatData();topk();return 0;
}

实现的思路：

先实现自定义数据交换函数，向下调整算法（时间复杂度低，所以选择它），生成随机数的函数。

其次就是实现Top-K问题的核心了，先定义可以自定可在所有数字要找最大的k个数字的变量k,然后再以读的形式打开所生成随机数的那个文件，再就是开辟k个数据大小的数组空间。

然后先将文件中前k个数据存储在该数组中，再进行将数组中的k个元素进行建堆处理（此处建的是小堆）。随后循环读取文件中剩余的数据（直到遇到文件结束的标志），每一次将从文件中读取中的数据和小堆的堆顶进行比较大小，如果比堆顶数据大就将该值堆顶位置（或者交换）。于此同时之后每次还得数据调整（一直保持小堆）。读取完比较调整完之后，将最终数组中的数据打印在终端上。最终需要关闭文件哦！！！

注：

   对于Top-k 问题如果求前K个最大的数据，就建小堆，反之就建小堆。   

 》》   》》》》》》》》》 今天分享的内容就结束了，下篇见》》》》》》》》》》》》》》》

关注博主，优质内容不断更新！！！

如有错误，还望指出！