揭秘Top-K问题：算法探索、性能优化与应用场景深度解析

鸽芷咕

发布于 2023-12-25 15:18:25

3960

发布于 2023-12-25 15:18:25

文章被收录于专栏：C++干货基地C++干货基地

🎬 鸽芷咕：个人主页 🔥 个人专栏: 《linux深造日志》《高效算法》

⛺️生活的理想，就是为了理想的生活!

文章目录

一、什么是 TOPK 问题？
二、日常生活中的 TOPK 问题
- 2.1 美团店面排行
- 2.2 软件排行榜
- 2.3 富豪榜
三、TOPK 问题的实现代码
- 3.1 TOK问题的核心思想
- 3.2 数据文件的创建
- 3.2 TOK问题的代码测试
📝文章结语：

一、什么是 TOPK 问题？

Top-K 问题是一类常见的算法问题，其中目的是从一组元素中找到排名前K的元素。具体来说，对于给定的一组数据。

Top-K 问题要求找到其中最大（或最小）的K个元素。

二、日常生活中的 TOPK 问题

Top-K 问题要求找到其中最大（或最小）的K个元素，这类问题我们的生活中也经常遇到，例如排名问题？

例如找出排名最高的 5 家店铺，这就要根据销量来算了
淘宝效率最高的5个店铺这些都需要用到 TOPK 问题

2.1 美团店面排行

2.2 软件排行榜

2.3 富豪榜

三、TOPK 问题的实现代码

TOPK问题大家第一时间想到的当让当然就是排序但排序的消耗太大了，我们只需要找到前 100 名但要把整个数据全部排序好。

而我们刚好学了堆这个是数据结构
每次堆顶要不就是最大或者最小的

而需要前100名的时候就先把，前100 个数据建。然后再和堆顶进行比较进行向下调整，这样整个数据的前100是不就被排出来了。

3.1 TOK问题的核心思想

🔥 前 TOP 个数据建堆，每次拿堆顶和剩下数据进行比较，进行向下调整。

这样我们建的堆就是最大或最小的前 TOP个数

📚 代码演示：

void PrintTopK(const char* filename, int k)
{
	// 1. 打开数据文件建堆--用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
	//开辟堆空间
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	//录入数据
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	//建堆
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		adjustdown(minheap, k, i);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			adjustdown(minheap, k, 0);
		}
	}

	free(minheap);
	fclose(fout);
}

🔥 注：这里采用的是文件打开方式有些书上可能给的是一个数组接收原理都是一样的！

3.2 数据文件的创建

📚 代码演示：

void TestTopk()
{
	// 造数据
	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);
	//PrintTopK(a, n, 10);
}

3.2 TOK问题的代码测试

这里拿了一千万个数据进行比较可以看到，只需要几秒钟就出来了大家可以去试验一下。

📝文章结语：

☁️ 把本章的内容全部掌握，铁汁们就可以熟练应用switch语句啦！ 看到这里了还不给博主扣个： ⛳️ 点赞🍹收藏 ⭐️ 关注！ 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要！ 你们的点赞就是博主更新最大的动力！ 有问题可以评论或者私信呢秒回哦。