【数据结构】——解决topk问题

前言：我们前面已经学习了小堆并且也实现了小堆，那么我们如果要从多个数据里选出最大的几个数据该怎么办呢，这节课我们就来解决这个问题。我们就用建小堆的方法来解决。

首先我们来看到这个方法的时间复杂度，我们先取前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万的数进行测试：

那么我们放入的数据就打印出来了。最后感谢大家的支持！