数据结构——堆排序的topk问题

本文介绍: 我们先建一个可以储存k 个数据的小堆，把文件里前k个的数先存入小堆中，如果在遍历这一百个万个数，只要比堆顶的数据大就把它插入堆顶，然后先下调整，循环往复这个堆里就会挤满一百万数中前k大的数了。利用的就是小堆中大的数都在下面不会堵住里堆顶，以至于后面的数进不来。

呀哈喽，我是结衣

前言

今天给大家带来的堆排序的topk 问题。topk 就是在许多数中，找出前k个大的数，可能是几十个数，也可能是几千万个数中找。今天我们将要在1000000（一百万）个数中找出前10大的数。

知识点

C语言文件的读写
建堆
向下调整排序
 随机数的产生
ps 向下调整和向上调整的教学都在我的另一篇文章堆的实现当中，不懂的小伙伴可以先学习堆的实现

topk的实现

文件的读取

文件的读取非常简单把w改为r就可以了

FILE* fin = fopen(file, "r");//只读方式
	if (fin == NULL)
	{
		perror("file errorn");
		return;
	}

我们要把一百万个数里前k个的大数找出来，是建小堆还是建大堆。
给大家3秒钟的时间思考：
3
2
1
那么答案是建小堆，为什么呢？小堆就是小的数据在上，大的数据在下。我们先建一个可以储存k个数据的小堆，把文件里前k个的数先存入小堆中，如果在遍历这一百个万个数，只要比堆顶的数据大就把它插入堆顶，然后先下调整，循环往复这个堆里就会挤满一百万数中前k大的数了。利用的就是小堆中大的数都在下面不会堵住里堆顶，以至于后面的数进不来。

建立小堆

我们假设k为10，就是说找前10大的数，那么我们就要建立一个空间为10的小堆：

int* a = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; i++)
	{
		fscanf(fin, "%d", &amp;a[i]);//将文件中的数写入数组当中
		adjustup(a, i);//向上调整，建立小堆。
	}

向上调整

void adjustup(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child&gt;0)
	{
		if (a[child] < a[parent])
		{
			swap(a,child, parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
		
	}
}

遍历文件

在这里我们要了解，写入数据到文件中时会在最后加入一个EOF，所以只要我们读到EOF就退出循环，

int x = 0;
	while (fscanf(fin, "%d", &amp;x) != EOF)
	{
		if (x &gt; a[0])
		{
			a[0] = x;
			adjustdown(a, 0, k);
		}
	}

在遍历当中我们把比堆顶大的数替换原来的堆顶，然后向下调整，形成新的小堆。

向下调整

void adjustdown(HpDataType* a, int parent, int size)
{
	int child = parent * 2 + 1;
	if (a[child] &gt; a[child + 1])
	{
		child++;
	}
	while (child < size)
	{
		//if (child+1<size &amp;&amp; a[child] &gt; a[child + 1])//inpustion
		//{
		//	child++;
		//}
		if (a[parent] &gt; a[child])
		{
			swap(a, child, parent);
			parent = child;
			child = parent * 2 + 1;
			if (child+1<size&amp;&amp;a[child] &gt; a[child + 1])//inpustion
			{
				child++;
			}
		}
		else
		{
			break;
		}
	}
}

交换 函数

void swap(HpDataType*a,int child, int parent)
{
	HpDataType tmp = a[child];
	a[child] = a[parent];
	a[parent] = tmp;
}

完整 代码

void Createnode()
{
	int n = 1000000;
	srand(time(0));
	char file[] = "data.txt";
	FILE* fin = fopen(file, "w");//只写方式
	if (fin == NULL)
	{
		perror("file errorn");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand()+i) % 1000000;//rand只能产生3万个随机数。
		fprintf(fin, "%dn", x);
	}
	fclose(fin);
}
void PrintTopK(FILE* file,int k)
{
	FILE* fin = fopen(file, "r");//只读方式
	if (fin == NULL)
	{
		perror("file errorn");
		return;
	}
	int* a = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; i++)
	{
		fscanf(fin, "%d", &amp;a[i]);
		adjustup(a, i);
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
	printf("n");
	int x = 0;
	while (fscanf(fin, "%d", &x) != EOF)
	{
		if (x > a[0])
		{
			a[0] = x;
			adjustdown(a, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
	fclose(fin);
}

int main()
{
	Createnode();
	int k = 0;
	scanf("%d", &k);
	PrintTopK("data.txt", k);
	return 0;
}

运行 效果

在这里插入图片描述

第二行为文件前10个数据小堆数据

当然最后你也可能会问，万一不是呢？这可是一百万个数啊，就算它随便打印，你也不知道是不是对的吧。emmm，你说的对，但是忍心让我用人力在这一百万个数据里面找吗。开玩笑啦，我当然有办法了，无奖竞猜，你会怎么办呢？
方法就是，我们来改数据，我们在文件里随机改几个数据让它一定会大于其他的数据，然后我们在看它有没有被打印出来。
ok，我现在偷偷改10个数据。我改里5个数，随机改的再让我们看看打印结果吧。
在这里插入图片描述