前言：我们前面已经学习了小堆并且也实现了小堆，那么我们如果要从多个数据里选出最大的几个数据该怎么办呢，这节课我们就来解决这个问题。我们就用建小堆的方法来解决。
首先我们来看到这个方法的时间复杂度，我们先取前k个数据建立一个小堆，后面插入的数据依次与堆顶对比，比堆顶小就不进入堆，比堆顶大就代替堆顶进入堆，在进行向下调整。时间复杂度为O(N*logK)。
创造随机数，存入文件：
void CreateNDate()
{
// 造数据
int n = 10000000;
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) % 10000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
我们设置1000万个1000万以内的数，并且将它存入文件。
我们打开文件的路径在点开文件就可以找到我们生成的随机数了。
我们来看看如何建堆：
void PrintTopK(const char* file, int k)
{
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
// 建一个k个数小堆
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc error");
return;
}
// 读取前k个，建小堆
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
AdjustUp(minheap, i);
}
int x = 0;
while (fscanf(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]);
}
printf("\n");
free(minheap);
fclose(fout);
}
因为我们取前k个数据来建立一个小堆，我们比堆顶大的数据就代替堆顶在向下调整沉到堆底。我们再将堆依次从文件中读取出来，如果我们读取出来的数据大于堆顶元素，就代替堆顶进行向下调整，最后在打印堆就可以打印出来前k个大的数据了。
测试代码：
int main()
{
CreateNDate();
PrintTopK("Data.txt", 5);
return 0;
}
如果我们在文件中改入几个大于1000万的数进行测试：
文章来源：https://www.toymoban.com/news/detail-759305.html
那么我们放入的数据就打印出来了。最后感谢大家的支持！文章来源地址https://www.toymoban.com/news/detail-759305.html
到了这里，关于【数据结构】——解决topk问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
