为了同学都能访问网站如何做,怎么做北京赛车网站,课件模板下载免费,营口化工网站建设大家好#xff0c;我是苏貝#xff0c;本篇博客带大家了解堆的TopK问题#xff0c;如果你觉得我写的还不错的话#xff0c;可以给我一个赞#x1f44d;吗#xff0c;感谢❤️ 目录 一. 前言二. TopK三. 代码 一. 前言
TOP-K问题#xff1a;即求数据结合中前K个最大的元… 大家好我是苏貝本篇博客带大家了解堆的TopK问题如果你觉得我写的还不错的话可以给我一个赞吗感谢❤️ 目录 一. 前言二. TopK三. 代码 一. 前言
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决 二. TopK
思路:
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
下面我们用找出1000000个元素中最大的5个值举例
1 为1000000个元素赋值
1000000个元素当然不可能是由我们手动赋值我们想到有srand函数搭配time函数可以生成随机值。 以写的形式打开文件data.txt如果文件不存在就会建立该文件。 我们知道srand(time(0))能生成的随机值只有3万多个这就意味着如果我们只用随机数赋值的话会有将近997万的数据是重复的所以我们在随机数的基础上再加一个会变的数这样重复的数字就会比较少。 最后将随机数写入文件中。
void CreateData()
{FILE* fin fopen(data.txt, w);if (fin NULL){perror(fopen fail);return;}int n 1000000;srand(time(0));for (int i 0; i n; i){int x 0;x (rand() i) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}在上面代码的操作下我们能保证所有的随机值都1000000那我们如何确保最后的结果是正确的呢我们可以在执行完这个函数后再打开文件随意修改5个值让它们都1000000这样最后的值只能是我们修改了的。
注意 在修改完5个值后将调用main函数中调用CreateData函数的代码注释掉否则再次运行程序文件里的数据会重新被修改
2 如何建小堆
1.先定义一个指针指向k个元素的数组 2.将文件的前k个元素边插入边向上调整最后得到小堆
了解fscanf
//void swap(int* a, int* b)
//{
// int tmp *a;
// *a *b;
// *b tmp;
//}//void AdjustUp(int* a, int child)
//{
// assert(a);
//
// 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;
// }
//}FILE* fout fopen(file, r);if (fout NULL){perror(fopen fail);return;}//1.建有k个元素的小堆int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(fopen fail);return;}//2.将前k个元素插入小堆中for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);AdjustUp(minheap, i);}3 要找出最大的k个值时为什么不用大堆
因为如果最大值先出来就占据了堆顶的位置此时次大值就因为最大值而不能进入大堆中。
4 得到TopK
用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素再将新的堆顶元素向下调整
//void AdjustDown(int* a, int size, int parent)
//{
// assert(a);
//
// int child parent * 2 1;
// while (child size)
// {
// if (child 1 size a[child 1] a[child])
// {
// child;
// }
// if (a[child] a[parent])
// {
// swap(a[child], a[parent]);
// parent child;
// child parent * 2 1;
// }
// else
// {
// break;
// }
// }
//
//}//3.遍历如果有数比堆顶元素大的话让堆顶元素该元素再向下调整while (fscanf(fout, r) ! EOF){int x 0;fscanf(fout, %d, x);if (x minheap[0]){minheap[0] x;AdjustDown(minheap, k, 0);}}三. 代码
#includestdio.h
#includeassert.h
#includestdlib.h
#includetime.h//构建数据
void CreateData()
{FILE* fin fopen(data.txt, w);if (fin NULL){perror(fopen fail);return;}int n 1000000;srand(time(0));for (int i 0; i n; i){int x 0;x (rand() i) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void AdjustUp(int* a, int child)
{assert(a);int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}void AdjustDown(int* a, int size, int parent)
{assert(a);int child parent * 2 1;while (child size){if (child 1 size 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 PrintTopK(FILE* file, int k)
{FILE* fout fopen(file, r);if (fout NULL){perror(fopen fail);return;}//1.建有k个元素的小堆int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(fopen fail);return;}//2.将前k个元素插入小堆中for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);AdjustUp(minheap, i);}//3.遍历如果有数比堆顶元素大的话让堆顶元素该元素再向下调整while (fscanf(fout, r) ! EOF){int x 0;fscanf(fout, %d, x);if (x minheap[0]){minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}free(minheap);fclose(fout);
}//TopK 找出最大的k个值
int main()
{//CreateData();PrintTopK(data.txt, 5);return 0;
}好了那么本篇博客就到此结束了如果你觉得本篇博客对你有些帮助可以给个大大的赞吗感谢看到这里我们下篇博客见❤️
相关文章：
