Top-K问题

2023-12-27 16:38:46

什么是Top-K问题问题呢?

TOP-K 问题:即求数据结合中 前K个最大的元素或者最小的元素 ,一般情况下 数据量都比较大
相信大家都听过或者玩过王者荣耀等游戏,里面就有什么国服玩家,省级打野等等,那么它是怎么知道数以亿的玩家谁是国服呢?这其实就可以看成TOP-K,当然实际肯定还包括其他部分内容。
好了,现在你明白什么是TOP-K 问题了,我想问你如何从那么多中找的你想要的呢?又是如何比较谁大谁小呢?
如果你没有思路,不妨听听我的见解。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用来解决

?

此时你是否感觉好像会一点了。有了模糊的思路?

那么我们继续,堆解决的话,我们首要任务就是建堆,那么如何建呢?所有元素都放一起去建堆吗?那肯定不行啊,所以我们是不是可以先用前K个元素来建堆,然后通过后续调整来实现我们的目标呢?

建K个元素的堆已经明确了,假如我们的目标是找最大的K个元素,问题来了,我们是建大堆还是小堆?你不妨想想?
?

我告诉你吧,我们这里要建小堆,为什么?

如果你是建的大堆,再向里面进元素的话,你是不是要调整啊,那么你肯定要比较吧?我问你,你和谁比呢?堆顶吗?向下调整法然后删除谁呢?是不是感觉很难实现,这种可能可以成功,但是肯定是建小堆简单,不信?看好了哈

接下来开始我的表演了

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <assert.h>
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int* tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Adjustup(int* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void Adjustdown(int* arr, int n, int parent)
{
	assert(arr);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if ((child + 1 < n) && (arr[child + 1] < arr[child]))
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child= parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void TopK(int k)
{
	//第一步:打开文件,找到要的数据
	FILE* pf = fopen("data.txt", "r");
	//判断是否打开失败
	if (pf == NULL)
	{
		perror(pf);
		return;
	}

	//第二步:建里一个K个大小的小堆(注意我们是找最大的K个数)
	//由于我们空间为空,首先我们我们先开辟空间
	int* head = (int*)malloc(sizeof(int) * k);
	//检查开辟成功与否
	if (head == NULL)
	{
		perror(head);
		return;
	}
	//开始建小堆,小堆!!!(提醒)
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &head[i]);
		//我们要对其进行调整
		Adjustup(head, i);
	}

	//第三步:我们要开始读取后面的元素,比较后看看能否放入堆中
	int x = 0;
	while ((fscanf(pf, "%d", &x)) != EOF)//这里我们一定要注意:fscanf是继续上次读取的位置继续读
	{
		//由于我们建的是小堆,如果比堆顶大的话,一定是可以放入堆中
		if (x > head[0])
		{
			head[0] = x;
			Adjustdown(head, k, 0);
		}
	}

	//第四步:输出最大的K个元素
	Print(head, k);

	//第五步:关闭文件,指针指向空
	head = NULL;
	fclose(pf);
}

int main()
{
	//Creat();
	int k = 5;
	TopK(k);
	return 0;
}

如果你对堆不是有了一定的学习,肯定看不懂这个代码,但是如果你写过堆实现和堆排序,上面代码你肯定可以理解,如果你想学堆实现和堆排序,可以看看我之前写的:

堆的实现(C语言版)-CSDN博客

堆排序(C语言版)-CSDN博客

如果你文件操作也不会的话,我也有:

C语言之?件操作-CSDN博客

希望你可以实现它们,加油!

void Creat()
{
	int n = 10000000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror(pf);
		return;
	}
	//实现产生随机数
	for (int i = 1; i < n; i++)
	{
		//注意:随机数只有三万个左右,所以我们通过+i来调整
		int x = (rand() + i) % 10000000;
		fprintf(pf, "%d\n", x);
	}
	//关闭文件
	fclose(pf);
	pf = NULL;
}

这个是我用来验证代码的,设立了这个文件之后,你可以去里面设置你可以验证自己代码正确性的数据。

最后:

我们强调下:

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

希望我们可以继续加油,努力学习吧!

文章来源:https://blog.csdn.net/2301_79813267/article/details/135241883
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。