堆排序和Topk问题

堆排序

堆排序即利用堆的思想来进行排序,

总共分为两个步骤:

1. 建堆 升序:建大堆;   降序:建小堆

2 .利用堆删除思想来进行排序

利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。

建堆

我们建堆的也利用我们的向下调整来建立我们的堆,但是我们不从我们的根开始,因为如果从根开始的话可以用我们的向上调整建堆,但是时间会比我们的向下调整建堆。

我们向下调整的是用是从底下开始,使我们的分支是一个堆,然后在使我们的整体是一个堆。

向下调整来排序

这里的排序和我们的堆的数据的删除相似。我们将我们的根和数组的最后一个元素进行交换后,我们的count--,在将剩下的元素进行向下调整,那么数组的最后的数字就是我们的最大的数字或者最小的数字。我们进行调整完我们堆 的根就是我们第二小(大)的数字,如此在进行交换和调整这样我们的数组就会变成有序的(升序或者降序)(我们这里写的是降序)。

总代码:

//对数组进行堆排序
void HeapSort(int* a, int n)
{
	//建堆
	int i = 0;
	int count = n;
	for (i = (n-1-1)/2; i>=0; i--)
	{
		AdjustDown(a, i, n);
	}
	for (i = 0; i < n; i++)
	{
		Swag(&a[0], &a[n - i - 1]);
		count--;
		AdjustDown(a, 0,count );
	}
}

Topk问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。 比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。

最佳的方式就是用堆来解决,基本思路如下:

1. 用数据集合中前K个元素来建堆 前k个最大的元素,则建小堆 前k个最小的元素,则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素。

当我们所有的数据比完后,这个堆中就只剩下我们的最大的或者最小的前k个数。这样需要的空间不会很大。

代码:

//创建数据,放在文件里面,随机数。
void CreakData()
{
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("FILE* fin eorror");
		return;
	}
	srand((unsigned int)time(0));
	int i = 0;
	for (i = 0; i < 100000; i++)
	{
		int count = rand() % 100000;
		fprintf(fin, "%d ", count);
	}
	fclose(fin);

}
//解决topk问题
void  PrintTopK(int k)
{
	//topK问题
	int* topk = (int*)malloc(sizeof(int) * k);
	if (topk == NULL)
	{
		perror("malloc");
	}
	int i = 0;
	int count = 0;
	//创建数据
	/*CreakData();*/
	//打开文件
	FILE* fin = fopen("data.txt", "r");
	if (fin == NULL)
	{
		perror("fopen!");
		return;
	}
	//读取前面k个数字
	for (i = 0; i < k; i++)
	{
		fscanf(fin, "%d", &topk[i]);
	}
	//建堆
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(topk, i, k);
	}
	//开始往后面读取数字,如果比我们的堆顶的数字大就和我们堆顶的数字交换
	//fsanf的返回值是他读取到字符个数.
	while (fscanf(fin, "%d", &count) == 1)
	{
		if (count > topk[0])
		{
			//交换并调整,使它形成新的堆
			topk[0] = count;
			AdjustDown(topk, 0, k);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ", topk[i]);
	}
	fclose(fin);
	free(topk);
}

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

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

相关文章

Go 错误日志处理

是不是所有的 if err ! nil 的地方都应该输出错误日志&#xff1f; 打印过多的错误日志会导致日志文件变得冗长和难以阅读。 其次&#xff0c;重复的错误信息会增加冗余。 此外&#xff0c;每一层都打印错误日志&#xff0c;一旦错误信息设计不当&#xff0c;可能会导致上下…

VCRUNTIME140_1.dll丢失是怎么回事?vcruntime140_1.dll无法继续执行代码的处理方法

VCRUNTIME140_1.dll丢失是怎么回事&#xff1f;问出这样的问题的人&#xff0c;一般是遇到vcruntime140_1.dll无法继续执行代码的问题了&#xff0c;找不到VCRUNTIME140_1.dll文件&#xff0c;那么程序就肯定是启动不了的&#xff0c;程序的启动是需要VCRUNTIME140_1.dll文件的…

全局数据 与 singleton 类的选择

1&#xff0c;singleton 相对于全局数据的优势 使用 Singleton 类相对于全局数据具有以下好处&#xff1a; 1.1. 延迟初始化&#xff1a;Singleton 类可以实现延迟初始化&#xff0c;即在需要时才创建实例&#xff0c;而全局数据在程序启动时就会被初始化。这可以节省资源并提…

设计软件有哪些?建模和造型工具篇(3),渲染100邀请码1a12

这次我们接着介绍建模工具。 1、FloorGenerator FloorGenerator是由CG-Source开发的3ds Max插件&#xff0c;用于快速创建各种类型的地板和瓷砖。该插件提供了丰富的地板样式和布局选项&#xff0c;用户可以根据需要轻松创建木质地板、石板地板、砖瓦地板等不同风格的地面。F…

【常用的队列总结】

文章目录 队列的介绍Queue队列的基本概念与操作队列的基本概念 常见的队列介绍非阻塞队列LinkedList:ArrayDeque:PriorityQueue: 阻塞队列ArrayBlockingQueueLinkedBlockingQueuePriorityBlockingQueue DelayQueueSynchronousQueue 队列的介绍 Queue队列的基本概念与操作 在 …

使用html2canvas和jspdf导出pdf包含跨页以及页脚

首先要下载两个文件&#xff0c;一个为html2canvas.min.js&#xff0c;另一个是jspdf.umd.min.js这两个文件分别下载的地址我也附录上&#xff0c;都在官网git&#xff1a; html2canvas.min.js: https://html2canvas.hertzen.com/dist/html2canvas.min.js jspdf.umd.min.js: …

Docker 快速搭建 MongoDB 4.x 集群(一主一从)

目录 1. 生成 mongo-file2. 启动主节点3. 启动从节点4. 配置副本集5. 注意事项 环境&#xff1a;MongoDB 4.0.25&#xff0c;Alma Linux&#xff08;建议使用 Linux&#xff09; 部署的时候是在同一个及其上操作的&#xff0c;实际可以放在不同机器上。 截止到 2024年05月&…

OceanBase数据库诊断调优,与高可用架构——【DBA从入门到实践】第八期

在学习了《DBA从入门到实践》的前几期课程后&#xff0c;大家对OceanBase的安装部署、日常运维、数据迁移以及业务开发等方面应当已经有了全面的认识。若在实际应用中遇到任何疑问或挑战&#xff0c;欢迎您在OceanBase社区问答论坛中交流、讨论。此次&#xff0c;《DBA从入门到…

如何学到数据库从入门到入土(MySQL篇)

本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人能接…

以太坊现货ETF获批:引发ETH价格暴涨,市场热议达到高潮

2024年5月24日&#xff0c;北京时间&#xff0c;以太坊现货ETF正式获得美国证券交易委员会&#xff08;SEC&#xff09;的批准&#xff0c;成为继比特币之后&#xff0c;美国主权政府承认的又一加密货币基金产品。这一意外的利好消息引发了加密货币市场的狂欢&#xff0c;以太坊…

阳光电源临摹品引发的EMC正向设计思考

画画可以临摹。画电路板临摹的人更多。 抄板&#xff0c;抄的是过去的板子&#xff0c;容易出问题。现在市场竞争激烈&#xff0c;欧美客户对出口产品的标准要求推陈出新&#xff0c;防不胜防。由于市场的竞争&#xff0c;欧洲客户已经意识到EMC电磁兼容的重要性&#xff0c;不…

【PID算法详解】

PID算法 PID算法介绍用途pid数学表达式及其含义P算法D算法I算法 PID总结数学公式转换代码设计实际运用PID代码实现 PID算法介绍 PID控制器是一种广泛应用于工业控制系统的反馈控制器&#xff0c;它通过比例&#xff08;Proportional&#xff09;、积分&#xff08;Integral&am…

LeetCode450删除二叉搜索树中的节点

题目描述 给定一个二叉搜索树的根节点 root 和一个值 key&#xff0c;删除二叉搜索树中的 key 对应的节点&#xff0c;并保证二叉搜索树的性质不变。返回二叉搜索树&#xff08;有可能被更新&#xff09;的根节点的引用。一般来说&#xff0c;删除节点可分为两个步骤&#xff1…

合约的值类型

基本数据类型&#xff1a;整数、枚举、布尔&#xff08;类似java的数据类型&#xff09;Address、Contract&#xff08;这两种是solidity特有的数据类型&#xff09;Fixed byte array&#xff08;定长字节数组&#xff09; Integer(int/uint) int/uint 以8位字节递增&#xf…

代码随想录算法训练营Day2|977.有序数组的平方、59.螺旋矩阵||、 209.长度最小的子数组

977.有序数组的平方 这道题给出的原数组有两个特点&#xff1a; 1、由小到大 2、有负数有正数 因此&#xff0c;这个数组平方后的数应该是从两头向中间的0减小的&#xff0c;但是两头的大小需要我们用两个指针便历之后去判断大小。在遍历的同时left指针向右走&#xff0c;righ…

Spring使用的设计模式

Spring 框架是一个广泛使用的 Java 框架&#xff0c;它内部使用了多种设计模式来简化开发过程、提高代码的可维护性和扩展性。 以下是一些在 Spring 框架中常见的设计模式&#xff0c;以及用代码示例来解释它们&#xff1a; 一、工厂模式&#xff08;Factory Pattern&#xff…

DIYGW UniApp可视化开发工具:前端开发人员的新宠

在前端开发的领域中&#xff0c;API接口的测试与调试一直是开发人员面临的挑战之一。传统的测试工具虽然能够完成基本的测试任务&#xff0c;但在效率、易用性和直观性方面仍有提升的空间。随着技术的发展&#xff0c;DIYGW UniApp可视化工具应运而生&#xff0c;为开发人员提供…

智慧园区:打造未来城市的新模式

随着城市化进程的加速和科技创新的推动&#xff0c;城市面临着诸多挑战和机遇。如何提升城市的竞争力和可持续性&#xff0c;是一个亟待解决的问题。在这个背景下&#xff0c;智慧园区作为一种新型的城市发展模式&#xff0c;引起了越来越多的关注和探索。 什么是智慧园区&…

gitlab将本地文件项目上传至gitlab服务

打开gitlab网页界面&#xff0c;登陆管理员账号 &#xff08;测试服务器安装的gitlab&#xff0c;浏览器输入ip或配置的gitlab地址&#xff09; 创建新项目 使用gitlab创建项目 创建一个新项目&#xff08;忽略分组&#xff09; &#xff08;忽略分组&#xff09; 在创建工…

CSS文本粒子动画特效之爱心粒子文字特效-Canvas

1. 效果图 2.完整代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><style>body,html {margin: 0;paddin…