【数据结构初阶】--- 堆的应用:topk

堆的功能:topk

为什么使用topk

先举个例子,假如说全国有十万家奶茶店,我现在想找到评分前十的店铺,现在应该怎么实现?
第一想法当然是排序,由大到小排序好,前十就能拿到了。这是一种方法,但我觉得不太方便,因为我要排序就得需要数组先去存放这十万个数据,如果是100w,或是一亿个数据呢,这个时候要用4亿个字节存放这些数据,4亿个字节大概是多少内存我们来算算,1G == 1024MB == 1024*1024KB ==1024*1024*1024byte == 10亿。1G能存放10亿个字节,那么4亿个字节差不多就是400MB,你要对这些数据进行排序就需要400MB,空间的代价显而易见,很多情况下这些数据并不是在一个内存里存放着,而是在文件中,文件中的内容是存放在硬盘中的,因为硬盘空间大,而内存相比之下就很小。那么想拿到这些数据中最大的前十个,步骤也就是,将文件中的数据读取在从内存中开辟好的空间,再进行排序,找到前十个数。总而言之,直接排序会有很大的空间消耗。

什么是topk

接下来我来讲解topk是什么

  1. 把前k个数建成小堆
  2. 后面N-k个数,依次比较,如果比堆顶数据大,就替换他进堆
  3. 最后这个小堆的值就是最大的前k个

思路:

我想要在这些数据中找到前十个最大的数,那我就先向内存中开辟十个数的空间,再读取前十个数(文件中最前面的十个数),同时将这是个数构建成一个小堆,之后从文件中每读取一个数据都与堆顶元素比较,如果大于堆顶元素,就用当前读取到的数覆盖这个堆顶元素,再进行向下调整;如果小于对顶元素那就读下一个数据,一直重复到结束,最终,小堆中的是个元素就是所有数据中最大的十个数。

验证加演示如何应用

  1. 先创建一个文件“test.txt”
  2. 生成10000个小于一万的数,并且写入到文件中
void CreateNData()
{
	Heap hp;
	HeapInit(&hp);
	srand((unsigned int)time(NULL));

	char* file = "test.txt";
	FILE* pf = fopen(file, "w");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}
	for (int i = 0; i < 10000; i++)
	{
		int x = rand() % 10000;
		fprintf(pf, "%d\n", x);
	}

	fclose(pf);
}

在这里插入图片描述

  1. 打开文件,现在文件中已经有了随机生成的一万个数
    在这里插入图片描述
  2. 我们现在要找这一万个数中最大的前五个,为了清楚是哪五个数,我们手动修改五个数让它们变成最大,方便观看,我就挨着调整了5个数
    在这里插入图片描述
  3. 此时我们就要实现一个topk的功能,先建立一个大小为5的小堆,再将文件中每一个数据与堆顶元素比较,如果大于堆顶元素就取代该堆顶元素,再进行向下调整
void PrintTopk(int k)
{
	char* file = "test.txt";
	FILE* pf = fopen(file, "r");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * 10);
	//先从文件中读取最前面的十个元素并且建立小堆
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &kminheap[i]);
		AdjustUp(kminheap, i+1);
	}
	int val = 0;
	while (!feof(pf))//读到文件尾返回非0,读到数据返回0
	{
		fscanf(pf, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

	//打印堆中元素
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}

在这里插入图片描述
6. 再次运行,因为刚才已经生成了数据并且我们修改了5个数据,如果再调用CreatNData()就会重新生成一万个数据覆盖掉原来的
在这里插入图片描述
好了,已经找到最大的前五个数据

如果想找最小的数据,那就建立大堆,随之,向上向下调整的代码只需更改判断父亲和孩子间大小的符号就行

时间复杂度计算·

时间复杂度计算,按照最坏的情况,那么就是,每个数与堆顶元素比较时都比堆顶元素大,因此需要交换,需要向下调整,那么最坏的情况就是每次要调整到最下层,现在堆中有5个数,3层,所以要调整两次,现在一共有N个数,大概就要调整N*2次,最大调整次数与层数有关,层数又与堆的节点数有关,层对应了节点的范围,h层对应节点数k的范围是[2(h-2)+1,2(h-1)],而调整次数是h-1,因此调整次数与节点数k有了初步地关系,调整次数==logk,一个数据调整一次是logk,所有数据调整的次数就为N*logk

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/719036.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

三星(中国)投资公司线上入职测评笔试邀请数字推理语言逻辑真题题库

三星&#xff08;中国&#xff09;有限公司北京分公司 邀请您参加 SHL线上笔试 具体安排如下&#xff1a; 笔试时间&#xff1a;周三 9:00 笔试时长&#xff1a;1.5h ~ 2h 笔试内容及要求&#xff1a;数字推理限时30min&#xff1b;语言逻辑限时30min&#xff1b;性格测试不…

【机器学习】第5章 朴素贝叶斯分类器

一、概念 1.贝叶斯定理&#xff1a; &#xff08;1&#xff09;就是“某个特征”属于“某种东西”的概率&#xff0c;公式就是最下面那个公式。 2.朴素贝叶斯算法概述 &#xff08;1&#xff09;是为数不多的基于概率论的分类算法&#xff0c;即通过考虑特征概率来预测分类。 …

你对SSH协议了解吗

SSH&#xff08;Secure Shell&#xff09;协议&#xff0c;作为网络通信领域的一项核心技术&#xff0c;以其卓越的安全性能和广泛的应用范围&#xff0c;成为保障网络通信安全的重要工具。本文将深入剖析SSH协议的工作原理、核心特性以及在现代网络通信中的关键作用&#xff0…

HTML静态网页成品作业(HTML+CSS)——新媒体专业介绍介绍网页(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…

经历的分享

我是三本计算机科学技术跨考上岸的学生&#xff0c;本科阶段技术能力并没有掌握多少&#xff0c;在选择导师时屡屡碰壁&#xff0c;我当时向许多计算机方向的导师&#xff0c;比如大数据方向,计算机视觉 迁移学习和图像处理方向的导师全都拒绝了我&#xff0c;最终学校给我分配…

SpringCloudStream原理和深入使用

简单概述 Spring Cloud Stream是一个用于构建与共享消息传递系统连接的高度可扩展的事件驱动型微服务的框架。 应用程序通过inputs或outputs来与Spring Cloud Stream中binder对象交互&#xff0c;binder对象负责与消息中间件交互。也就是说&#xff1a;Spring Cloud Stream能…

Sunny v1.3.0 官方版 (简洁且漂亮截图应用)

前言 Sunny是一款漂亮又实用的“截图&钉图”的软件&#xff0c;亦支持“屏幕识图”和“OCR”的软件。 一、下载地址 下载链接&#xff1a;http://dygod/source 点击搜索&#xff1a;Sunny 二、安装步骤 1、解压后将Sunny.exe发送到桌面快捷方式 2、启动桌面图标 3、正…

下载lombok.jar包,简化类的代码

Download (projectlombok.org) 去这个网站下载lombok.jar包 打开这个包文件的位置,拖到项目lib文件夹: 在这里右键添加为库(Add as library)。 添加这三个注解即可&#xff0c;类里面不需要其他东西了

手写操作系统

对喜欢操作系统的伙伴强推一门课程 从0开始实现了支持文件系统、任务切换和网络协议栈的操作系统。 具体见 &#xff1a;http://www.ziyuanwang.online/977.html

012.指纹浏览器编译-修改canvas指纹(高级)

指纹浏览器编译-修改canvas指纹(高级) 一、canvas指纹是什么 之前介绍过canvas指纹和常见网站绕过canvas指纹&#xff0c;插眼&#xff1a; https://blog.csdn.net/w1101662433/article/details/137959179 二、为啥有更高级的canvas指纹 众所周知&#xff0c;creepjs和brow…

Java Lambda表达式:简洁代码的艺术与实战技巧

引言 Java Lambda表达式是Java SE8中引入的一项重要的语言特性&#xff0c;它允许我们以简洁的方式去编写代码&#xff0c;同时也能大大提高代码的可读性和编写的灵活性。结合Java8及以后版本中引入的Stream API&#xff0c;Lambda表达式使得集合操作变得更为直观和强大。本文将…

Codeforces Round 953 (Div. 2 ABCDEF题) 视频讲解

A. Alice and Books Problem Statement Alice has n n n books. The 1 1 1-st book contains a 1 a_1 a1​ pages, the 2 2 2-nd book contains a 2 a_2 a2​ pages, … \ldots …, the n n n-th book contains a n a_n an​ pages. Alice does the following: She …

Centos7如何扩容未做lvm的GPT硬盘

背景&#xff1a;一台根分区为2.5T(已转换GPT格式)的虚拟机使用率达到97%&#xff0c;需要扩容&#xff0c;但是又没做lvm 通过平台新增容量1.5T&#xff0c;如下可看到 安装growpart准备扩容&#xff1a; yum install cloud-utils-growpart -y 执行命令growpart报错&#xff…

11 数制介绍及转换

数制介绍 一、数制介绍 &#xff08;一&#xff09;计算机的数制 ​ 二进制这个词的意思是基于两个数字 ​ 二进制数或二进制位表示为0 和1 ​ 示例&#xff1a;10001011 ​ 十进制数制系统包括10 个数字&#xff1a;十进制数0、1、2、3、4、5、6、7、8、9 ​ 示例&…

性能测试项目实战

项目介绍和部署 项目背景 轻商城项目是一个现在流行的电商项目。我们需要综合评估该项目中各个关键接口的性能&#xff0c;并给出优化建议&#xff0c;以满足项目上线后的性能需要。 项目功能架构 前台商城&#xff1a;购物车、订单、支付、优惠券等 后台管理系统&#xf…

【挑战100天首通《谷粒商城》】-【第一天】06、环境-使用vagrant快速创建linux虚拟机

文章目录 课程介绍1、安装 linux 虚拟机2、安装 VirtualBoxStage 1&#xff1a;开启CPU虚拟化Stage 2&#xff1a;下载 VirtualBoxStage 2&#xff1a;安装 VirtualBoxStage 4&#xff1a;安装 VagrantStage 4-1&#xff1a;Vagrant 下载Stage 4-2&#xff1a;Vagrant 安装Stag…

如何确保pcdn的稳定性?(壹)

确保PCDN的稳定性是一个重要任务&#xff0c;涉及多个方面的操作和考虑。以下是一些建议&#xff0c;帮助你确保PCDN的稳定性&#xff1a; 一&#xff0e;选择合适的服务器与硬件&#xff1a; 选择稳定可靠的服务器供应商和硬件设备&#xff0c;确保服务器具有高可用性和容错…

图说设计模式:单例模式

更多C学习笔记&#xff0c;关注 wx公众号&#xff1a;cpp读书笔记 5. 单例模式 单例模式 模式动机模式定义模式结构时序图代码分析模式分析实例优点缺点适用环境模式应用模式扩展总结 5.1. 模式动机 对于系统中的某些类来说&#xff0c;只有一个实例很重要&#xff0c;例如…

我在高职教STM32——GPIO入门之蜂鸣器

大家好&#xff0c;我是老耿&#xff0c;高职青椒一枚&#xff0c;一直从事单片机、嵌入式、物联网等课程的教学。对于高职的学生层次&#xff0c;同行应该都懂的&#xff0c;老师在课堂上教学几乎是没什么成就感的。正因如此&#xff0c;才有了借助 CSDN 平台寻求认同感和成就…

聚四氟乙烯离心管 四氟反应管 消解管 PTFE螺口带盖管 特氟龙试管

一、产品介绍 样品悬浮液盛放在管状试样容器中&#xff0c;在离心机的高速旋转下&#xff0c;由于巨大的离心力作用&#xff0c;使悬浮的微小颗粒 以一定的速度沉降&#xff0c;从而与溶液得以分离。这种带密封盖或压盖的管状试样容器&#xff0c;就是离心管。 PTFE离心管&…