堆的应用——堆排序和TOP-K问题
1.堆排序
想法⼀:
基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构(之前的文章有讲解),去实现排序。
void HeapSort(int* a, int n){HP hp;for(int i = 0; i < n; i++){HPPush(&hp,a[i]);}int i = 0;while (!HPEmpty(&hp)){a[i++] = HPTop(&hp);HPPop(&hp);}HPDestroy(&hp);
先依次入堆,然后再将堆顶,数据依次取出,为大堆即是降序,小堆为升序。实际上这种方法使用起来是很不方便的,必须要有堆的数据结构,而且时间复杂度为O(n)。
想法⼆:
数组建堆,⾸尾交换,交换后的堆尾数据从堆中删掉,将堆顶数据向下调整选出次⼤的数据。
void HeapSort(int* arr, int n)
{//根据给定的arr来进行建堆//child:n-1 parent:(n-1-1)/2向下调整算法建堆//for (int i = (n - 1 - 1) / 2; i >= 0; i--)//O(n)//{// AdjustDown(arr, i, n);//O(logn)//}//向上调整建堆for (int i = 0; i < n; i++){AdjustUp(arr, i);}//堆排序//排升序---建大堆//排降序---建小堆int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}}
这里利用的是堆的思想,而不是直接用堆来排序,首先要建堆,将传进来的数组入堆,这里以建小堆为例,利用向下调整的方法,将一个个依次调整直到,直到根节点;
这里完成了建堆,那后面接下来,排序怎么办,其实利用思想将堆顶元素,与最后一个元素交换,再将元素个数减一,将剩余的堆进行调整,依次交换直到到堆顶。最后发现建的小堆,其实是降序排列,反之降序是建小堆。
这样就排序完成。
注意:这里考虑一个问题,向上调整可以建堆,向下调整也可以建堆,那个时间复杂度更低。
1.2向上调整算法和向下调整算法比较:
向上调整算法:
往下结点个数逐渐增多,向下调整次数增多;
可以推出向上调整建堆时间的复杂度:O(n*logn);
向下调整算法:
可以推出向下调整建堆时间的复杂度:O(n);
比较发现向下调整算法更优。
2.TOP-K问题
TOP-K问题:即求数据结合中前K个最⼤的元素或者最⼩的元素,⼀般情况下数据量都⽐较⼤。 ⽐如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题,能想到的最简单直接的⽅式就是排序,但是:如果数据量⾮常⼤,排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决,基本思路如下:
第一步:⽤数据集合中前K个元素来建堆
(这和前面堆排序有一些相似)
前k个最⼤的元素,则建⼩堆;
前k个最小的元素,则建⼤堆;
第二步:⽤剩余的N-K个元素依次与堆顶元素来⽐较,不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后,堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素
void TopK()
{int k = 0;printf("请输入K:");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最大的前K个数,建小堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//读取文件中前K个数据建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minHeap, i, k);}//遍历剩下的n-k个数据,跟堆顶比较,谁大谁入堆//调整堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);
}
这里一些文件操作函数,可以看看小编前面的文章有讲解。
相关文章:

堆的应用——堆排序和TOP-K问题
1.堆排序 想法⼀: 基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构(之前的文章有讲解),去实现排序。 void HeapSort(int* a, int n){HP hp;for(int i 0; i < n; i){HPPush(&hp,a[i]);}int i 0;whi…...

探秘 MySQL 数据类型的艺术:性能与存储的精妙平衡
文章目录 前言🎀一、数据类型分类🎀二、整数类型(举例 TINYINT 和 INT )🎫2.1 TINYINT 和 INT 类型的定义2.1.1 TINYINT2.1.2 INT 🎫2.2 表的操作示例2.2.1 创建包含 TINYINT 和 INT 类型的表2.2.2 插入数据…...

使用任意绘图软件自学并结合上课所学内容完成数据库原理图绘制
本次绘图采用亿图图示软件...

static、 静态导入、成员变量的初始化、单例模式、final 常量(Content)、嵌套类、局部类、抽象类、接口、Lambda、方法引用
static static 常用来修饰类的成员:成员变量、方法、嵌套类 成员变量 被static修饰:类变量、成员变量、静态字段 在程序中只占用一段固定的内存(存储在方法区),所有对象共享可以通过实例、类访问 (一般用类名访问和修…...

基于SSM的智能养生平台管理系统源码带本地搭建教程
技术栈与架构 技术框架:采用SSM(Spring Spring MVC MyBatis)作为后端开发框架,结合前端技术栈layui、JSP、Bootstrap与jQuery,以及数据库MySQL 5.7,共同构建项目。 运行环境:项目在JDK 8环境…...

Latex中文排版字体和字号
中文排版 最近常用latex排版,也遇到了很多问题。这里对于主要的参考文章做一个总结和推荐。 一份不太简短的 LaTeX2ε 介绍【中文资料】ctex宏包用户手册,用户手册使用 命令行texdoc ctex 这两个文档都是中文的,而且几乎解决了我90%的排版…...

[C++ 11] 列表初始化:轻量级对象initializer_list
C发展历史 C11是C语言的第二个主要版本,也是自C98以来最重要的一次更新。它引入了大量的新特性,标准化了已有的实践,并极大地改进了C程序员可用的抽象能力。在2011年8月12日被ISO正式采纳之前,人们一直使用“C0x”这个名称&#…...
【NodeJS】NodeJS+mongoDB在线版开发简单RestfulAPI (八):API说明(暂时完结,后续考虑将在线版mongoDB变为本地版)
本项目旨在学习如何快速使用 nodejs 开发后端api,并为以后开展其他项目的开启提供简易的后端模版。(非后端工程师) 由于文档是代码写完之后,为了记录项目中需要注意的技术点,因此文档的叙述方式并非开发顺序࿰…...

manictime整合两个数据库的数据
作用 老电脑崩溃了,有个1t.db, 新电脑有个3t.db 那么重装系统后就想整合起来用。 整合前文件大小 整合命令 .\mtdb.exe importtimelines -sdbpa ManicTimeCore-1t.db -dbpa ManicTimeCore-3t.db -tt ManicTime/ComputerUsage,ManicTime/Applications,ManicTime…...

Spring Boot植物健康系统:智慧农业的新趋势
6系统测试 6.1概念和意义 测试的定义:程序测试是为了发现错误而执行程序的过程。测试(Testing)的任务与目的可以描述为: 目的:发现程序的错误; 任务:通过在计算机上执行程序,暴露程序中潜在的错误。 另一个…...

(三)第一个Qt程序“Qt版本的HelloWorld”
一、随记 我们在学习编程语言的时候,各种讲解编程语言的书籍中通常都会以一个非常经典的“HelloWorld”程序展开详细讲解。程序虽然简短,但是“麻雀虽小,五脏俱全”,但是却非常适合用来熟悉程序结构、规范,快速形成对编…...
【Python知识】一个强大的数据分析库Pandas
文章目录 Pandas概述1. 安装 Pandas2. 基本数据结构3. 数据导入和导出4. 数据清洗5. 数据选择和过滤6. 数据聚合和摘要7. 数据合并和连接8. 数据透视表9. 时间序列分析10. 数据可视化 📈 如何使用 Pandas 进行复杂的数据分析?1. 数据预处理2. 处理缺失值…...
10.26学习
1.整形的定义和输出 在C语言中,整形(Integer)是一种基本数据类型,用于存储整数。整形变量可以是正数、负数或零。在定义和输出整形变量时,需要注意以下几点: ①定义整形变量: 使用 int 关键字…...

CSS易漏知识
复杂选择器可以通过(id的个数,class的个数,标签的个数)的形式,计算权重。 如果我们需要将某个选择器的某条属性提升权重,可以在属性后面写!important;注意!importent要写在;前面 很多公司不允许…...

【10天速通Navigation2】(三) :Cartographer建图算法配置:从仿真到实车,从原理到实现
前言 往期内容: 第一期:【10天速通Navigation2】(一) 框架总览和概念解释第二期:【10天速通Navigation2】(二) :ROS2gazebo阿克曼小车模型搭建-gazebo_ackermann_drive等插件的配置和说明 本教材将贯穿nav2的全部内容,…...

测试造数,excel转insert语句
目录 excel转sql的insert语句一、背景二、直接上代码 excel转sql的insert语句 一、背景 在实际测试工作中,需要频繁地进行测试造数并插入数据库验证,常规的手写sql语句过于浪费时间,为此简单写个脚本,通过excel来造数࿰…...

Python 应用可观测重磅上线:解决 LLM 应用落地的“最后一公里”问题
作者:彦鸿 背景 随着 LLM(大语言模型)技术的不断成熟和应用场景的不断拓展,越来越多的企业开始将 LLM 技术纳入自己的产品和服务中。LLM 在自然语言处理方面表现出令人印象深刻的能力。然而,其内部机制仍然不明确&am…...

从零开始:用Spring Boot搭建厨艺分享网站
2 相关技术 2.1 Spring Boot框架简介 Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置,从而使开发人员不再需要定义样板化的配置。通过这种方式,Sprin…...

《2024中国泛娱乐出海洞察报告》解析,垂直且多元化方向发展!
随着以“社交”为代表的全球泛娱乐市场规模不断扩大以及用户需求不断细化,中国泛娱乐出海产品正朝着更加垂直化、多元化的方向发展。基于此,《2024中国泛娱乐出海洞察报告》深入剖析了中国泛娱乐行业出海进程以及各细分赛道出海现状及核心特征。针对中国…...

强化学习数学原理学习(一)
前言 总之开始学! 正文 先从一些concept开始吧,有一个脉络比较好 state 首先是就是状态和状态空间,显而易见,不多说了 action 同理,动作和动作空间 state transition 状态转换,不多说 policy 策略,不多说 reward 奖励,不多说 MDP(马尔科夫) 这里需要注意到就是这个是无…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...

PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...