堆排序和Topk问题

news/2024/7/20 16:52:11/文章来源:https://blog.csdn.net/2301_80028974/article/details/139272705

堆排序

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

总共分为两个步骤:

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);
}

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

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

相关文章

260 基于matlab的工业乙醇发酵GUI仿真

基于matlab的工业乙醇发酵GUI仿真。首先对经典的流加半经验半理论模型进行动态和稳态仿真&#xff0c;考虑实际情况密&#xff0c;逐步将温度&#xff0c;气体排放等因素考虑到模型中去&#xff0c;进行综合性仿真。结合GUI技术&#xff0c;以动力学模型为核心&#xff0c;制作…

【组合数学 放球问题 虚拟点 小于等于转小于】1621. 大小为 K 的不重叠线段的数目

本文涉及知识点 放球问题 组合数学汇总 本题难道分&#xff1a;2198 LeetCode1621. 大小为 K 的不重叠线段的数目 给你一维空间的 n 个点&#xff0c;其中第 i 个点&#xff08;编号从 0 到 n-1&#xff09;位于 x i 处&#xff0c;请你找到 恰好 k 个不重叠 线段且每个线段…

VUE3+TS+elementplus+Django+MySQL实现从数据库读取数据,显示在前端界面上

一、前言 前面通过VUE3和elementplus创建了一个table&#xff0c;VUE3TSelementplus创建table&#xff0c;纯前端的table&#xff0c;以及使用VUE3TSelementplus创建一个增加按钮&#xff0c;使用前端的静态数据&#xff0c;显示在表格中。今天通过从后端获取数据来显示在表格…

大数据开发面试题【Kafka篇】

83、介绍下Kafka&#xff0c;Kafka的作用?Kafka的组件?适用场景? kafka是一个高吞吐量、可扩展的分布式消息传递系统&#xff0c;在处理实时流式数据&#xff0c;并能够保证持久性和容错性 可用于数据管道、流分析和数据继承和关键任务应用&#xff08;发布/订阅模式&#…

【Python】 Django 框架如何支持百万级日访问量

基本原理 Django 是一个高级的 Python Web 框架&#xff0c;它鼓励快速开发和干净、实用的设计。Django 遵循 MVC&#xff08;模型-视图-控制器&#xff09;设计模式&#xff0c;允许开发者通过编写更少的代码来构建高质量的 Web 应用程序。Django 自带了许多内置功能&#xf…

学习笔记——STM32F103V3版本——HC-05模块控制数码管

一.硬件 1.HC-05模块 2.数码管 3.连接硬件 二.在keil5中的代码 main.c代码&#xff1a; #include "stm32f10x.h" #include "buletooth.h" #include "led.h" #include "sys.h" #include "usart.h" #include "delay.…

目标检测数据集 - 工地工人安全设备佩戴检测数据集下载「包含VOC、COCO、YOLO三种格式」

数据集介绍&#xff1a;工地工人安全设备佩戴检测数据集&#xff0c;真实场景数据生成增强后高质量图片数据&#xff0c;涉及场景丰富&#xff0c;比如楼宇建筑工地工人作业数据、道路建筑工地工人作业数据、室内工地工人作业数据、露天挖掘场景工人作业数据、工地工人自拍摆拍…

SpringBoot+layuimini实现角色权限菜单增删改查(layui扩展组件 dtree)

角色菜单 相关组件方法效果图MySQL代码实现资源菜单树组件实现权限树方法js这里我先主要实现权限树的整体实现方法&#xff0c;如果是直接查看使用的话可以只看这里&#xff01; 后端代码Controlle层代码Service代码及实现类代码Service代码ServiceImpl代码 resourceMapper 代码…

斯坦福大学ALOHA家务机器人团队发布了最新研究成果—YAY Robot语言交互式操作系统

ALOHA YAY 演示视频-智能佳 斯坦福的ALOHA家务机器人团队&#xff0c;发布了最新研究成果—Yell At Your Robot&#xff08;简称YAY&#xff09;&#xff0c;有了它&#xff0c;机器人的“翻车”动作&#xff0c;只要喊句话就能纠正了&#xff01; 标ALOHA2协作平台题 而且机器…

破解微信校验难题,Xinstall助你轻松实现Universal Link功能!

在移动互联网时代&#xff0c;App的推广和运营离不开各种技术手段的支持。其中&#xff0c;Universal Link作为连接App和网页的重要桥梁&#xff0c;被广大开发者所青睐。然而&#xff0c;很多开发者在使用Universal Link时遇到了微信校验不通过的问题&#xff0c;这不仅影响了…

数据库语法树优化

目录 一、σ、π、⋈ 1.选择σ 2.投影π 3.连接⋈ 二、 构建语法树 ① 解读sql语句 ② 写出关系代数表达式 ③ 画出语法树 三、优化语法树 四、练习 语法树优化方法 一、σ、π、⋈ 1.选择σ 选择就是在关系R中选择满足给定条件的诸元组。 通过条件SdeptIS选择出系别…

基于C#开发web网页管理系统模板流程-主界面管理员录入和编辑功能完善

前言 紧接上篇->基于C#开发web网页管理系统模板流程-登录界面和主界面_c#的网页编程-CSDN博客 已经完成了登录界面和主界面&#xff0c;本篇将完善主界面的管理员录入和编辑功能&#xff0c;事实上管理员录入和编辑的设计套路适用于所有静态表的录入和编辑 首先还是介绍一下…

Android环境下Mesa初始化流程重学习之eglInitialize

Mesa初始化流程重学习之eglInitialize 引言 说来也惭愧&#xff0c;Mesa搞了这么久了&#xff0c;每次都想深入下&#xff0c;可是每次都是浅尝辄止了。这次趁着有了一定的闲暇时间并且有了调试景嘉微显卡的机会&#xff0c;还是想重新学习下&#xff0c;深入研究下&#xff0…

【软件设计师】——5.数据库系统

目录 5.1 基本概念 5.2 三级模式两级映射 5.3 设计过程和数据模型 5.4 关系代数 5.5 完整性约束 5.6 规范化和反规范化 5.7 控制功能 5.8 SQL语言 5.9 数据库安全 5.10 数据备份 5.11 数据库故障与恢复 5.12 数据仓库、数据挖掘和大数据 5.1 基本概念 相关术语 候选…

12.可视化实现

时间过的很快,不知不觉已到第十二章。经过前面教程的讲解和实践,数据接入服务的功能已初步完成。 此章节将通过可视化的实现,对设备接入进行监控,实时监听设备的接入情况及设备的在线时长。 并且可以通过订阅按钮、取消订阅按钮、查看数据按钮,对上报数据进行实时的跟踪…

AWS容器之Amazon ECS

Amazon Elastic Container Service&#xff08;Amazon ECS&#xff09;是亚马逊提供的一种完全托管的容器编排服务&#xff0c;用于在云中运行、扩展和管理Docker容器化的应用程序。可以理解为Docker在云中对应的服务就是ECS。

OC IOS 文件解压缩预览

热很。。热很。。。。夏天的城市只有热浪没有情怀。。。 来吧&#xff0c;come on。。。 引用第三方库&#xff1a; pod SSZipArchive 开发实现&#xff1a; 一、控制器实现 头文件控制器定义&#xff1a; // // ZipRarViewController.h // // Created by carbonzhao on 2…

手搓顺序表(C语言)

目录 SeqList.h SeqList.c 头插尾插复用任意位置插入 头删尾删复用任意位置删除 SLtest.c 测试示例 顺序表优劣分析 SeqList.h //SeqList.h#pragma once#include <stdio.h> #include <assert.h> #include <stdlib.h> #define IN_CY 3typedef int S…

系统管理、磁盘分区

系统管理 业务层面&#xff1a;为了满足一定的需求所做的特定操作。 硬盘是什么&#xff0c;硬盘的作用&#xff1a; **硬盘&#xff1a;**计算机的存储设备&#xff0c;机械硬盘是由一个或者多个磁性的盘组成&#xff0c;可以在盘片上进行数据的读写。 连接方式&#xff1a…

开源VS闭源:谁将引领AI大模型的新时代?

一、引言 随着人工智能技术的飞速发展&#xff0c;AI大模型已成为推动这一浪潮的核心动力。在AI大模型的发展过程中&#xff0c;开源与闭源两种不同的发展路径一直备受关注。本文将深入探讨这两种路径的优劣势&#xff0c;分析它们对AI大模型发展的影响&#xff0c;并预测谁将…