前言

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

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

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

问题分析

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

答案是：建小堆

代码实现

<code>#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的是在原有数据上手动添加的

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