堆的应用：Top-K问题网站首页 其他

堆的应用：Top-K问题

stackY、 2024-07-18 00:01:02

简介堆的应用：Top-K问题

朋友们、伙计们，我们又见面了，本期来给大家解读一下堆的应用--Top-K问题的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

数据结构与算法专栏：数据结构与算法

个人主页 ：stackY、

C 语言专栏：C语言：从入门到精通

前言：

前面我们学了堆的实现、堆排序算法，堆排序算法中我们知道了使用堆排序要向下调整建堆，排升序我们建的是大堆、排降序我们建小堆，其中的细节就不做赘述，堆排序算法让我们初步了解了堆这种特殊的数据结构的作用，那么在本篇再来给大家带来一个关于堆的应用的问题：Top-K问题。

1.何为Top-K

TopK问题指的是在一个包含N个元素的序列中，找出其中前K个最大或者最小的元素。通常情况下，K远小于N，因此这个问题也被称为“求前K大（小）元素”问题。TopK问题在数据分析、排序算法、搜索引擎等领域都有着广泛的应用。

举个栗子：

在100000个随机数数中找出前10个最大的数。

2.解题思路

TopK问题在这里有多种解决的办法，我们取最优解：

1. 对N个数据进行从小到大或者从大到小排序，然后取出前K个数据便是我们想要找的数据。

2. 联想我们学过的堆排序，将这N个数建立大堆或者小堆，依次取出前K个数据即可。

但是这两种方法都存在一个问题：首先排序本身就是比较费劲的事情，如果N非常大，排序需要的代价很大，并且将N个数建堆也不合理，因为数据过多计算机内存容纳不下那么多的数据，就会存储到磁盘文件中，我们知道数据在磁盘文件中处理的速度是比较慢的，因此我们需要想一个更方便的方法（假设要在N个数据中找前K个最大的数据）。

改进方法：

1. 先建立K个数的小堆

2. 再用后面N-K个数依次插入，如果比堆顶的数据大，就替换进堆

3. 最后这个小堆中的数据就是要找的前K个数。

3.代码演示

3.1创建数据

我们为了来演示代码的正确性，我们先来创建数据，将10W个数据先保存在一个文件中，然后找出这10W个数据中最大的前五个数据。这里就需要用到文件操作的相关知识（进阶C语言：文件操作）和一个随机数的种子（猜数字小游戏）。

代码演示：
//创建数据
void CreateNDate()
{
	int n = 100000;           //总数据个数
 	srand((unsigned int)time(NULL));  //设置随机数生成器
	const char* file = "data.txt";
	//打开文件
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fial");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//数据范围在10W之内
		int x = rand() % 100000;
		//写文件
		fprintf(fin, "%d
", x);
	}
	//关闭文件
	fclose(fin);
	fin = NULL;
}

3.2建小堆、排序

先建K个数的小堆，然后使用剩下的N-K个数据依次插入比较，比堆顶大的数据就替换进堆,然后向下调整，直到将文件中的所有数据比较完成，这时这个K个数的堆就是我们要找的数据（这里建小堆为什么不建大堆？因为小堆的堆顶的元素是这个堆中最小的元素，如果有比它大的就可以筛选进入堆，如果建成大堆，那么堆顶的数就是最大的，那么遇到次大的就进不来，所以需要建小堆）。

代码演示：
void PrintTopK(int k)
{
	//打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fial");
		return;
	}
	//先建立K个数的小堆
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	//将文件中的前K个数据先储存在块空间中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	//向下调整将这K个数建成小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int num = 0;
	//文件读取结束表示排序完成
	while (!feof(fout))
	{
		//依次比较
		fscanf(fout, "%d", &num);
		//符合则进行替换，向下调整
		if (num > kminheap[0])
		{
			kminheap[0] = num;
			AdjustDown(kminheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("
");

	//关闭文件
	fclose(fout);
	fout = NULL;
}

4.完整代码

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


//Top - K问题

//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整
void AdjustDown(int* a, int n, int parent)
{
	//假设左孩子为左右孩子中最小的节点
	int child = parent * 2 + 1;

	while (child < n)  //当交换到最后一个孩子节点就停止
	{
		if (child + 1 < n  //判断是否存在右孩子
			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
		{
			child++;   //若不符合就转化为右孩子
		}
		//判断孩子和父亲的大小关系
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新父亲和孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//创建数据
void CreateNDate()
{
	int n = 100000;           //总数据个数
 	srand((unsigned int)time(NULL));  //设置随机数生成器
	const char* file = "data.txt";
	//打开文件
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fial");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//数据范围在10W之内
		int x = rand() % 100000;
		//写文件
		fprintf(fin, "%d
", x);
	}
	//关闭文件
	fclose(fin);
	fin = NULL;
}

void PrintTopK(int k)
{
	//打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fial");
		return;
	}
	//先建立K个数的小堆
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	//将文件中的前K个数据先储存在块空间中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	//向下调整将这K个数建成小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int num = 0;
	//文件读取结束表示排序完成
	while (!feof(fout))
	{
		//依次比较
		fscanf(fout, "%d", &num);
		//符合则进行替换，向下调整
		if (num > kminheap[0])
		{
			kminheap[0] = num;
			AdjustDown(kminheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("
");

	//关闭文件
	fclose(fout);
	fout = NULL;
}

int main()
{
	//创建数据
	CreateNDate();
	//求前5个最大数
	PrintTopK(5);
	return 0;
}