【C语言】Top K问题【建小堆】

前言

TopK问题：从n个数中，找出最大（或最小）的前k个数。

在我们生活中，经常会遇到TopK问题

比如外卖的必吃榜；成单的前K名；各种数据的最值筛选

问题分析

显然想开出40G的空间是不现实的，那应该怎么办呢？

答案是：建小堆

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<time.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的是在原有数据上手动添加的

重新运行，结果与预期一致