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

这篇具有很好参考价值的文章主要介绍了数据结构——堆排序的topk问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

呀哈喽,我是结衣

前言

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

知识点

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

文件的创建

随机数的生成

生成随机数我们要用到rand函数,但是因为rand函数生成随机数需要种子,所以我要还要用到srand函数为其生成种子
但问题又来了,随机种子哪来的,难道在用rand吗?这显然就不行了,那么time函数就要被我们利用了,time会根据时间的变化而该,所以我们就用time来生成随机种子。

srand(time(0));

time函数的头文件为<time.h>,srand和rand都为<stdlib.h>.

文件的写入

我们要在一百万个数中找前10大的数肯定不能直接把一百万个数打印在屏幕里吧,所以我们要把这一百万个数存放在文件data.txt中。
写入文件要用到fopen
数据结构——堆排序的topk问题,数据结构,数据结构,c语言,算法,笔记


void Createnode()
{
	int n = 1000000;
	srand(time(0));
	char file[] = "data.txt";
	FILE* fin = fopen(file, "w");//只写方式
	if (fin == NULL)//"w"表示只写的意思,if语句为了防止文件创建失败
	{
		perror("file error\n");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = rand()+i % 1000000;//rand只能产生3万个随机数,所以我们加个i
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

看看效果吧。
数据结构——堆排序的topk问题,数据结构,数据结构,c语言,算法,笔记
在记事本里生成了一百万个数,大约8mb。

topk的实现

文件的读取

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

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

topk思路

我们要把一百万个数里前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", &a[i]);//将文件中的数写入数组当中
		adjustup(a, i);//向上调整,建立小堆。
	}

向上调整

void adjustup(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>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", &x) != EOF)
	{
		if (x > 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] > a[child + 1])
	{
		child++;
	}
	while (child < size)
	{
		//if (child+1<size && a[child] > a[child + 1])//inpustion
		//{
		//	child++;
		//}
		if (a[parent] > a[child])
		{
			swap(a, child, parent);
			parent = child;
			child = parent * 2 + 1;
			if (child+1<size&&a[child] > 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 error\n");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand()+i) % 1000000;//rand只能产生3万个随机数。
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
void PrintTopK(FILE* file,int k)
{
	FILE* fin = fopen(file, "r");//只读方式
	if (fin == NULL)
	{
		perror("file error\n");
		return;
	}
	int* a = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; i++)
	{
		fscanf(fin, "%d", &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;
}

运行效果

数据结构——堆排序的topk问题,数据结构,数据结构,c语言,算法,笔记
数据结构——堆排序的topk问题,数据结构,数据结构,c语言,算法,笔记

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

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

数据结构——堆排序的topk问题,数据结构,数据结构,c语言,算法,笔记
我不小心又运行了Createnode();导致里面的数字重新打印了,所以第二行和上面不一样
大家看看是不是把我们刚刚改的数都打印上去了,这就是topk问题。

数据结构——堆排序的topk问题,数据结构,数据结构,c语言,算法,笔记文章来源地址https://www.toymoban.com/news/detail-766676.html

到了这里,关于数据结构——堆排序的topk问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 玩转堆排序以及Topk问题——【数据结构】

    W...Y的主页 😊 代码仓库分享  💕 目录 堆排序  建堆  建堆的时间复杂度 Topk问题 学习了二叉树以及堆,今天我们来学习一下什么是堆排序以及经典二叉树问题——topk问题。 在学习开始我们先来回顾一下上篇博客中我们提到的堆,在实现堆时我们要进行向上调整或向下调

    2024年02月07日
    浏览(35)
  • 【初阶数据结构】——堆排序和TopK问题

     ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏  ========================================================================= 接上篇二叉树和堆的引入 =========================================================================  目录 前言 建堆 插

    2024年02月07日
    浏览(42)
  • 数据结构:堆的应用(堆排序和topk问题)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 堆排序即是 先将数据建堆,再利用堆删除的思想来排序。 将待排序数组建堆 将堆顶数据与数组尾部数据交换 调整新的堆顶数据,使其保证堆的结构不变 重复2,3步直到堆中没有数据结束。 降序 建小堆 (父节点 小于

    2024年02月13日
    浏览(38)
  • 【数据结构之二叉树简介·顺序存储·应用:堆·堆排序·TOPK问题】

    ​ 🕺作者: 迷茫的启明星 😘欢迎关注:👍点赞🙌收藏✍️留言 🎃相关文章 【数据结构从0到1之树的初识】 【数据结构】带你学会二叉树的链式存储的前中后序遍历,遍历推导及利用队列实现二叉树的层次遍历。 🏇家人们,码字不易,你的👍点赞🙌收藏❤️关注对我

    2024年02月01日
    浏览(35)
  • 【数据结构】---TopK问题

    本文提供用建堆来解决TopK问题的一个思路 N个数中找出最大的或者最小的前k个 假设现从N个数中找最小的前k个 ①堆排序, 时间复杂度O(N*logN),这N个数排一下序,前k个数就是需要的 ②建堆N个数的小堆 ,HeapPop k-1 次,就选出来了,因为小堆最小的在堆顶,选出一次后,再删除

    2024年02月12日
    浏览(46)
  • 【数据结构】——解决topk问题

    前言:我们前面已经学习了小堆并且也实现了小堆,那么我们如果要从多个数据里选出最大的几个数据该怎么办呢,这节课我们就来解决这个问题。我们就用建小堆的方法来解决。 首先我们来看到这个方法的时间复杂度,我们先取前k个数据建立一个小堆,后面插入的数据依

    2024年02月04日
    浏览(40)
  • 【数据结构】【堆】 堆排,TOPK问题

    堆排序,就是先将数据构建成堆,根据需要构建大堆或者小堆。 如果要排降序,就构建小堆。 如果要排升序,就构建大堆。 我们 以降序为例 : 在构建好小堆后,堆顶的数据就是最小的。 我们将堆顶数据与最后一个数据进行交换,然后把堆的最后一个位置排除在外(即它不

    2024年02月07日
    浏览(35)
  • 【数据结构】堆的应用-----TopK问题

    目录 一、前言 二、Top-k问题   💦解法一:暴力排序 💦解法二:建立N个数的堆 💦解法三:建立K个数的堆(最优解) 三、完整代码和视图  四、共勉 在之前的文章中,已经详细的讲解了二叉树、堆、堆排序。那么关于堆还有一个比较有意思的题,就是TopK问题。 如果对堆

    2024年02月07日
    浏览(46)
  • 数据结构——堆的应用 Topk问题

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月14日
    浏览(58)
  • 数据结构——排序算法(C语言)

    本篇将详细讲一下以下排序算法: 直接插入排序 希尔排序 选择排序 快速排序 归并排序 计数排序 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某写的大小,按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中,存在多个

    2024年02月08日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包