【数据结构】详解堆排序当中的topk问题（leetcode例题）_数据结构

文章目录

前言
如何理解topk问题
代码逻辑
代码实现

前言

如何理解topk问题

当我们第一次接触这个问题时，我们会想到的方法可能是：

在这两个限制下，我们再去直接使用堆排序是不现实的，所以我们需要用一种更巧妙地方式，但代码的本质上仍然不离开堆排序；

代码逻辑

如果你需要找到最小的 k 个元素，只需在创建堆时使用最小堆即可

在这里我们通过堆排序的方法来讲解topk问题；

代码实现

//使用数组的前k个元素构造含有k个元素的小根堆
//从k+1开始遍历，每次和堆顶元素比较，若被遍历到的元素大于堆顶元素，则替换堆顶元素并调整堆，保证堆内的k个元素总是当前最大的k个元素。
void createndate()
{
	// 造数据
	int n = 100000;
	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);
}

void testheap3()
{
	int k;
	printf("请输入k>:");
	scanf("%d", &k);
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == null)
	{
		perror("malloc fail");
		return;
	}
	const char* file = "data.txt";
	file* fout = fopen(file, "r");
	if (fout == null)
	{
		perror("fopen error");
		return;
	}

	// 读取文件中前k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	// 11:51继续
	// 建k个数的小堆
	for (int i = (k-1-1)/2; i>=0 ; i--)
	{
		adjustdown(kminheap, k, i);
	}

	// 读取剩下的n-k个数
	int x = 0;
	while (fscanf(fout, "%d", &x) > 0)
	{
		if (x > kminheap[0])
		{
			kminheap[0] = x;
			adjustdown(kminheap, k, 0);
		}
	}

	printf("最大前%d个数：", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}