【数据结构】堆：TOK问题

前言

🐱个人主页： 代码探秘者
🐭C语言专栏：C语言
🐰C++专栏： C++ / STL使用以及模拟实现/C++11新特性
🐹数据结构专栏： 数据结构 / 十大排序算法
🐶 Linux专栏： Linux系统编程 / Linux网络编程（准备更新）
🌈喜欢的诗句:天行健,君子以自强不息.

问题引入

TopK 问题 (在一堆数据里面找到前 K 个最大 / 最小的数)。

一、TopK 问题 是什么？

生活中也有很多实例，比如某外卖软件中有上千家店铺，我想选出当地好评最多的十家烤肉店，这时我们不用对所有数据进行排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。

二、TopK 问题解决思路

2.1 TopK 思路

思路一： 将数组从小到大排序，拿到数组前3个元素。但是可以发现这样时间复杂度太高，不可取。

思路二： 将元素全部放入一个堆结构中，然后弹出三个元素，每次弹出的元素都是当前堆最小的，那么弹出的三个元素就是前最小的三个元素。
这种思路可以做，但是假设我有1000000个元素，只弹出前三个最小的元素，那么就要用到大小为1000000的堆。这么做**空间复杂度太高，**不建议用这种方法。

【最佳方法】-- 方法三：最佳的方式就是用堆来解决
基本思路如下：

1、用数据集合中前 K 个元素来建堆。

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2、用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
3.将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
————————————————

2.2 创建数据集

步骤1：生成随机数据
首先，我们需要生成一组随机数据，用于模拟实际场景中的数据集

//数据
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);
}

2.4 TOP-K问题求解

向下调整法

//数据个数		要从哪里开始向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	//第一步找出最小的孩子(然后和父亲交换)

	//假设法 走边孩子最小
	int minchild = parent * 2 + 1;
	while (minchild < n)	//当没到最后一个
	{
		//左孩子和右孩子（谁最小呢？）
		//1.前提右孩子存在吧		2.右孩子小于小孩子
		if (minchild + 1 < n && a[minchild + 1] < a[minchild])
		{
			minchild++;		//最小孩子下标更新为右孩子
		}
		//开始调整
		if (a[minchild] < a[parent])
		{
			Swap(&a[minchild], &a[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

Top-K问题求解

• 这段代码首先读取前K个数，并构建一个最小堆。

• 然后，它读取剩下的数据，并与堆顶元素进行比较。

• 如果新读取的元素大于堆顶元素，它将替换堆顶元素，并进行向下调整以维护堆的性质。

//TOP-K
void testHeap2()
{
	//N个数找最大的前K个
	//选最大的K个，先建一个前个K个数的小堆
	//打开
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}	int k;
	printf("请输入k>:");
	scanf("%d", &k);
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	int i = 0;
	for (i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);		//读入前k个数
	}
	//建k个数的小堆
	for (i = (k - 1 - 1) / 2; i >= 0; i++)
	{
		AdjustDown(kminheap,k,0);
	}
	//读取剩下的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");

}

2.5 验证结果

我把其中两个数据，改的超级大

找最大的两个