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

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