淄川网站建设yx718,怎样建免费个人网站,网站建设与 维护实训报告范文,淮南网云小镇最新消息前言
TopK问题#xff1a;从n个数中#xff0c;找出最大#xff08;或最小#xff09;的前k个数。 在我们生活中#xff0c;经常会遇到TopK问题
比如外卖的必吃榜#xff1b;成单的前K名#xff1b;各种数据的最值筛选
问题分析 显然想开出40G的空间是不现实的#…前言
TopK问题从n个数中找出最大或最小的前k个数。 在我们生活中经常会遇到TopK问题
比如外卖的必吃榜成单的前K名各种数据的最值筛选
问题分析 显然想开出40G的空间是不现实的那应该怎么办呢
答案是建小堆 代码实现
#includestdio.h
#includestdlib.h
#includetime.h// 造数据
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);
}
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py 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 PrintTopK(int k)
{FILE* fout fopen(data.txt, r);if (fout NULL){perror(fopen mail);return;}int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(minheap mail);return;}for (int i 0; i k; i){fscanf_s(fout, %d, minheap[i]);}//建小堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(minheap, k, i);}int x 0;int val 0;while (val fscanf_s(fout, %d, x) ! EOF){if (x minheap[0]){minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}fclose(fout);
}
int main()
{//CreateNDate();printf(请输入k);int k 0;scanf_s(%d, k);PrintTopK(k);return 0;
}运行结果 结果验证
那我们怎么确定输出在屏幕上的数据就是最大的数据呢
我们可以在已经创建的数据上面修改如图后面111的是在原有数据上手动添加的 重新运行结果与预期一致
