堆的应用：Top

2023-06-02 12:34| 来源: 网络整理| 查看: 265

朋友们、伙计们，我们又见面了，本期来给大家解读一下堆的应用--Top-K问题的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

数据结构与算法专栏：数据结构与算法

个人主页：stackY、

C 语言专栏：C语言：从入门到精通

前言：

前面我们学了堆的实现、堆排序算法，堆排序算法中我们知道了使用堆排序要向下调整建堆，排升序我们建的是大堆、排降序我们建小堆，其中的细节就不做赘述，堆排序算法让我们初步了解了堆这种特殊的数据结构的作用，那么在本篇再来给大家带来一个关于堆的应用的问题：Top-K问题。

1.何为Top-K

TopK问题指的是在一个包含N个元素的序列中，找出其中前K个最大或者最小的元素。通常情况下，K远小于N，因此这个问题也被称为“求前K大（小）元素”问题。TopK问题在数据分析、排序算法、搜索引擎等领域都有着广泛的应用。

举个栗子：

在100000个随机数数中找出前10个最大的数。

2.解题思路

TopK问题在这里有多种解决的办法，我们取最优解：

1. 对N个数据进行从小到大或者从大到小排序，然后取出前K个数据便是我们想要找的数据。

2. 联想我们学过的堆排序，将这N个数建立大堆或者小堆，依次取出前K个数据即可。

但是这两种方法都存在一个问题：首先排序本身就是比较费劲的事情，如果N非常大，排序需要的代价很大，并且将N个数建堆也不合理，因为数据过多计算机内存容纳不下那么多的数据，就会存储到磁盘文件中，我们知道数据在磁盘文件中处理的速度是比较慢的，因此我们需要想一个更方便的方法（假设要在N个数据中找前K个最大的数据）。

改进方法：

1. 先建立K个数的小堆

2. 再用后面N-K个数依次插入，如果比堆顶的数据大，就替换进堆

3. 最后这个小堆中的数据就是要找的前K个数。

3.代码演示 3.1创建数据

我们为了来演示代码的正确性，我们先来创建数据，将10W个数据先保存在一个文件中，然后找出这10W个数据中最大的前五个数据。这里就需要用到文件操作的相关知识（进阶C语言：文件操作）和一个随机数的种子（猜数字小游戏）。

代码演示：

//创建数据 void CreateNDate() { int n = 100000; //总数据个数 srand((unsigned int)time(NULL)); //设置随机数生成器 const char* file = "data.txt"; //打开文件 FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen fial"); return; } for (int i = 0; i < n; i++) { //数据范围在10W之内 int x = rand() % 100000; //写文件 fprintf(fin, "%d\n", x); } //关闭文件 fclose(fin); fin = NULL; } 3.2建小堆、排序

先建K个数的小堆，然后使用剩下的N-K个数据依次插入比较，比堆顶大的数据就替换进堆,然后向下调整，直到将文件中的所有数据比较完成，这时这个K个数的堆就是我们要找的数据（这里建小堆为什么不建大堆？因为小堆的堆顶的元素是这个堆中最小的元素，如果有比它大的就可以筛选进入堆，如果建成大堆，那么堆顶的数就是最大的，那么遇到次大的就进不来，所以需要建小堆）。

代码演示：

void PrintTopK(int k) { //打开文件 const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen fial"); return; } //先建立K个数的小堆 int* kminheap = (int*)malloc(sizeof(int) * k); if (kminheap == NULL) { perror("malloc fail"); return; } //将文件中的前K个数据先储存在块空间中 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &kminheap[i]); } //向下调整将这K个数建成小堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(kminheap, k, i); } int num = 0; //文件读取结束表示排序完成 while (!feof(fout)) { //依次比较 fscanf(fout, "%d", &num); //符合则进行替换，向下调整 if (num > kminheap[0]) { kminheap[0] = num; AdjustDown(kminheap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", kminheap[i]); } printf("\n"); //关闭文件 fclose(fout); fout = NULL; } 4.完整代码

#define _CRT_SECURE_NO_WARNINGS 1 #include #include #include //Top - K问题 //交换函数 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整 void AdjustDown(int* a, int n, int parent) { //假设左孩子为左右孩子中最小的节点 int child = parent * 2 + 1; while (child < n) //当交换到最后一个孩子节点就停止 { if (child + 1 < n //判断是否存在右孩子 && a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子 { child++; //若不符合就转化为右孩子 } //判断孩子和父亲的大小关系 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); //更新父亲和孩子节点 parent = child; child = parent * 2 + 1; } else { break; } } } //创建数据 void CreateNDate() { int n = 100000; //总数据个数 srand((unsigned int)time(NULL)); //设置随机数生成器 const char* file = "data.txt"; //打开文件 FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen fial"); return; } for (int i = 0; i < n; i++) { //数据范围在10W之内 int x = rand() % 100000; //写文件 fprintf(fin, "%d\n", x); } //关闭文件 fclose(fin); fin = NULL; } void PrintTopK(int k) { //打开文件 const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen fial"); return; } //先建立K个数的小堆 int* kminheap = (int*)malloc(sizeof(int) * k); if (kminheap == NULL) { perror("malloc fail"); return; } //将文件中的前K个数据先储存在块空间中 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &kminheap[i]); } //向下调整将这K个数建成小堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(kminheap, k, i); } int num = 0; //文件读取结束表示排序完成 while (!feof(fout)) { //依次比较 fscanf(fout, "%d", &num); //符合则进行替换，向下调整 if (num > kminheap[0]) { kminheap[0] = num; AdjustDown(kminheap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", kminheap[i]); } printf("\n"); //关闭文件 fclose(fout); fout = NULL; } int main() { //创建数据 CreateNDate(); //求前5个最大数 PrintTopK(5); return 0; }

可以看到在10W个数据中找到了前5个最大的数。

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！

【本文地址】

公司简介

联系我们