【数据结构】什么是堆?
🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境:Visual Studio 2022
堆的概念及结构
堆的定义如下:
n个元素的序列{k1,k2,...,kn}当且仅当满足以下关系时,称之为堆.
或
把这个序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有双亲结点的值均不小于(或不大于)其左,右孩子结点的值.
由此,若序列 {k1,k2,...,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最大值(或最小值).
如下面两个序列为堆(存储结构),则其对应的完全二叉树(逻辑结构)如下图所示:
综上,我们不难总结出堆的性质:
- 堆中某个结点的值总是不大于或不小于其父亲结点的值.
- 堆总是一颗完全二叉树.
堆的实现
有关堆结构的完整实现部分我放在下面这篇博客中为大家详细梳理了,并且为每个算法逻辑配备了详细明了的逻辑结构演示图和物理结构演示图,如:
对堆的实现部分的具体逻辑和细节感兴趣的朋友可以点击下方链接直接跳转到相应文章:
【数据结构】C语言实现堆(附完整运行代码)http://t.csdnimg.cn/v7qVo
建堆的时间复杂度
建堆有两种方式,一种是从堆顶开始向下建堆,另一种是从堆尾开始向上建堆.乍一听好像两种建堆方式除了向上调整和向下调整方式不同之外没什么区别,但我们仔细分析一下,其实这两种建堆方式的时间复杂度差别是很大的.
向上调整建堆
我们先一起来分析一下向上建堆的时间复杂度:
首先,按照算法算法最坏时间复杂度分析,我们假设堆是完全二叉树中的满二叉树,并且假设每个结点的移动次数都是最坏移动次数,则:
使用错位相消法,可得:
化简,可得:
使用大O阶渐近表示法,可得:
因为:
(舍去低次方阶和常数阶后剩下的2^h恰好是高为h的树的结点个数n,同样的h也可化简为以2为底n的对数)
向下调整建堆
再来看看向下调整建堆:
我们继续,按照算法最坏时间复杂度分析,假设堆是完全二叉树中的满二叉树,并且假设每个结点的移动次数都是最坏移动次数,则:
使用错位相消法,可得T(n)为:
化简,可得:
使用大O阶渐近表示法,可得:
T(n) = 2^h = O(n)
(舍去低次方阶和常数阶后剩下的2^h恰好是高为h的树的结点个数n)
综上可知:
- 向上调整的建堆方式的时间复杂度为
- 向下调整的建堆方式的时间复杂度为
- 向下调整建堆是优于向上调整建堆的.
堆思想的应用
1.堆排序
堆排序就是利用堆(假设利用大堆)进行排序(假设为升序)的算法.
它的基本思想是:
将待排序的序列构造成一个大堆.
此时,整个序列的最大值就是堆顶的根结点.将它移走(其实就是我们前面堆实现中的出堆顶操作).
然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次小值(即堆顶).
如此反复执行,就可以得到一个有序的序列了.
使用堆排序的思想排序有以下几点需要注意的:
- 排升序建大堆
- 排降序建小堆
- 建好堆后利用堆删除的思想进行排序
如下是一个顺序待排数组:
为了直观的利用堆排序的思想,我们在逻辑上将其还原为一颗完全二叉树:
我们先将数组视为一个空堆,开始时堆中没有元素.
我们先模拟一下向上建堆的过程:
即数组逐渐向后遍历,模拟向堆中插入元素:
(ps:此处建堆也可以使用向下建堆的思路,时间复杂度会更小,但要注意的是,向下建堆时,我们对数组的遍历是从最后一个叶子结点的父节点开始向前遍历并向下调整的.假设数组有n个元素,即是从下标为[(n-2)/2]的结点开始向前遍历并向下调整.)
插入'75':
插入'80':
向上调整:
插入'60':
我们先按照入堆的逻辑,将数组建成一个大堆:
然后再按照堆删除的思想,将堆顶元素移动至堆尾"删除":
再将换到堆顶的元素向下调整:
调整好后再删除"新的堆顶元素":
如此循环"删除堆顶":
最终就会得到一个升序的序列:
2.Top-k问题
Top-k问题:
即求数据集合中前k个最大/最小的元素,一般情况下数据量都比较大.
对于Top-k问题,最容易想到的方法是先整体排序,再取前k个,但当数据量非常大时(可能都无法加载到内存上),排序就不是一个很好的解决方法了.
这时的最佳的方案就是用堆来解决,思路如下:
1.先用数据元素中前K个元素来建堆
- 求前k个最大的元素,则建小堆
- 求前k个最小的元素,则建大堆
2.遍历剩余的N-K个元素来比较,遇到符合条件的(如求前k个最大的元素,新元素比堆顶要大)则用其替换堆顶,然后再向下调整,构建为新的大堆/小堆.
3.当遍历完剩下N-K个元素时,堆中剩余的k个元素就是所求的前Top-k个元素.
这个思路有点类似于让一个堆里最"弱"的元素去守"门",如果新来的元素比最弱的强,则让它替换最弱的进堆,再在堆中选出新的最弱的去"守门".如果新来的元素比最弱的还弱,那它就完全不是我们要找的元素,可以直接把它pass掉.
利用这种方式选出top-k,当数据量大到可以忽略建堆以及后续调整堆部分的操作带来的时间复杂度时,我们可以近似的认为这个算法的时间复杂度为O(n).
结语
希望这篇有关数据结构"堆"的文章能对您有所帮助,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
相关文章推荐
【数据结构】C语言实现堆(附完整运行代码)【数据结构】什么是线性表?
【数据结构】线性表的链式存储结构
【数据结构】什么是栈?
【数据结构】用C语言实现顺序栈(附完整运行代码)
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】10道经典面试题目带你玩转链表
相关文章:

【数据结构】什么是堆?
🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 堆的概念及结构 堆的定义如下: n个元素的序列{k1,k2,...,kn}当且仅当满足以下关系时,称之为堆. 或 把这个序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个…...

生产环境_Spark处理轨迹中跨越本初子午线的经度列
使用spark处理数据集,解决gis轨迹点在地图上跨本初子午线的问题,这个问题很复杂,先补充一版我写的 import org.apache.spark.{SparkConf, SparkContext} import org.apache.spark.sql.{Row, SparkSession} import org.apache.spark.sql.func…...

Vue前端与后端放在一起的搭建方式
1.首先把后端项目搭建好 去到项目的存放位置 2.然后cmd黑窗口输入命令创建vue项目 3.创建成功后回到后端项目进行合并 3.1在File处选择Project Structure 3.2选择模块 3.3找到自己的vue项目 3.4疯狂next最后create 3.5选择Apply并确定OK,恭喜您创建成功了 二、启动…...

SI24R03国产自主可控RISC-V架构MCU低功耗2.4GHz收发芯片SoC
目录 RISC-V架构的优势SI24R03/04特性射频收发器模块特征MCU 模块特征 其他特征 RISC-V架构的优势 相对于目前主流的英特尔X86架构及ARM等架构来说,RISC-V架构具有指令精简、模块化、可扩展、开源、免费等优点。RISC-V的基础指令集只有40多条,加上其他基…...

基于FPGA的温度控制系统设计(论文+源码)
1.系统设计 本次基于FPGA的智能温度控制系统,以FPGA为控制核心,采用自顶向下的设计方法,按照模块化设计的思路分别实现各个模块,再加以整合实现整个系统,从而达到了温度控制的目的。系统以水箱为被控对象,…...

C语言训练:三个字符串比较大小,实现两个整数数的交换统计二进制中1的个数
目录 一、编写程序,输入三个字符串,比较它们的大小,并将它们按由小到大的顺序输出。要求用函数、指针实现。要求:要采用函数调用,并用指向函数的指针作为函数的参数。 1.不使用函数指针作为参数,并自己模拟strcmp。 …...

module ‘tensorflow‘ has no attribute XXX 报错解决
问题描述: 粘了别人的tensorflow项目,运行总是报错module ‘tensorflow’ has no attribute什么什么 问题解决: 导入tensorflow的代码如下 import tensorflow as tf此时,某个某块报错,比如下面这个 那么就直接把tf.…...

MySQL数据库 DDL
目录 一、DDL 二、操作数据库 三、操作表 四、数据类型 五、表操作案例 六、修改表 七、删除表 一、DDL Data Definition Language,数据定义语言,用来定义数据库对象(数据库,表,字段) 。 二、操作数据库 (1&am…...

力扣二叉树--总结篇(2)
前言 总体回顾:11.18-12.14,中间有一个星期左右因为考试没有写题。37道题。 内容 这是第二阶段刷的题 从路径到构造二叉树,合并二叉树,再到二叉搜索树,公共祖先问题 看到二叉树,看到递归 都会想&#…...

小米移动端页面练习---重点:导航栏点击下箭头内容的切换以及样式,高亮显示的实现
效果图 1.html <div><header><div class"header-ad"><img src"./images/ad.png" alt"" srcset""></div><div class"header-two-section"><div class"logo"><div c…...

从零开始创建一个项目,springBoot+mybatisPlus+mysql+swagger+maven
一,前提 从零开始创建一个项目,绑定了数据库 用到的技术栈:springBootmybatisPlusmysqlswaggermaven 二,创建项目步骤 1,创建项目 创建出来的项目结构如图所示 2,修改配置文件 因为我比较习惯yml语言&…...

【视点合成】代码解读:生成demo视频
变换工具 def render_3dphoto(src_imgs, # 输入的源图像,维度为 [batch_size, 3, height, width]mpi_all_src, # 输入的所有源图像的MPI,维度为 [batch_size, num_planes, 4, height, width]disparity_all_src, # 所有源图像的视差信息&…...

Process On在线绘制流程图
目录 一.ProcessOn 1.1.介绍 1.2.直接网上使用 二.绘制门诊流程图 三.绘制住院流程图 四.绘制药库采购入库流程图 五.绘制OA会议流程图 今天就到这里了哦!!!希望能帮到你哦!!! 一.ProcessOn 1.1.介绍 ProcessOn(流程&#…...

【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive
【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive 1)压缩文件2)上传文件到 OBS 存储对象3)crontab 定时压缩上传4)从 obs 上拉取下来文件后解压缩5)判断对应文件是否存在6࿰…...

直线检测算子
hough_lines_dir 接口 hough_lines_dir(ImageDir : HoughImage, Lines : DirectionUncertainty, AngleResolution, Smoothing, FilterSize, Threshold, AngleGap, DistGap, GenLines : Angle, Dist) 参数 in: ImageDir :由边缘检测算子sobel_dir、edge_image获取的…...

如何在本地Docker中部署MinIO服务并实现远程访问管理界面
文章目录 前言1. Docker 部署MinIO2. 本地访问MinIO3. Linux安装Cpolar4. 配置MinIO公网地址5. 远程访问MinIO管理界面6. 固定MinIO公网地址 前言 MinIO是一个开源的对象存储服务器,可以在各种环境中运行,例如本地、Docker容器、Kubernetes集群等。它兼…...

逛商场。。。
题目名字 逛商场 题意 见到想买的物品,只要能买得起,就一定会买下来之后才会继续往前走;如果买不起就直接跳过 思路 接着,它读取数组 aa 的值,并存储在数组中。然后,程序读取一个整数 m。初始化计数器 cn…...

RTrPPG
研究背景 心率 (HR) 和脉搏率变异性 (PRV) 是允许分析心脏行为的两个生理参数。心率监测可以通过接触式和非接触式的两种方法进行。通常用于测量 HR 和 PRV 的两种接触式技术是心电图 (ECG) 和光电容积脉搏波 (PPG)。 ECG 测量由心脏活动引起的电场。另一方面,PPG …...

web应用开发技术的一些概念
一、Servlet 1.Servlet的工作过程: Servelt的工作流程示意图 (1)客户端发起一个Http请求到服务器,请求特定的资源或者是要执行特定的操作 (2)服务器在接收到请求后,根据请求相应的URL将请求分发…...

智能优化算法应用:基于乌燕鸥算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于乌燕鸥算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于乌燕鸥算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.乌燕鸥算法4.实验参数设定5.算法结果6.参考文…...

超聚变服务器(原华为服务器)网站模拟器
一、超聚变服务器(原华为服务器)网站模拟器: 原来了解服务器可以从他的网站上进行了解,模拟器做的很好了。 https://support.xfusion.com/server-simulators/ 有很多的模拟器,今天主要看下BMC的设置 有很多的在线工具…...

Linux常见压缩指令小结
为什么需要压缩技术 我们都知道文件是以byte作为单位的,如果我们的文件仅仅在低位占一个1 0000 0001这种情况我们完全可以压缩一下,将高位的0全部抹掉即可。 如上所说是一种压缩技术,还有一种就是将1111(此处省略96个)一共100个1࿰…...

OpenSSL的源码在哪里下载?
官方网站去下载,网址: https://www.openssl.org/source/ 比较老的版本的下载页面地址: https://www.openssl.org/source/old/ 由于某面板的OpenSSL模块的安装配置语句如下: --with-openssl/root/rpmbuild/BUILD/openssl-1.0.2u所…...

使用create-react-app脚手架创建react项目
文章目录 1、安装create-react-app脚手架2、创建 React 项目,项目名为 react-demo3、项目创建成功4、使用vscode打开项目并运行5、项目运行成功node_modules:存放项目所依赖的一些第三方包文件public:静态资源文件夹src:源码文件夹其它文件 1…...

【网络安全】网络防护之旅 - 点燃网络安全战场的数字签名烟火
🌈个人主页:Sarapines Programmer🔥 系列专栏:《网络安全之道 | 数字征程》⏰墨香寄清辞:千里传信如电光,密码奥妙似仙方。 挑战黑暗剑拔弩张,网络战场誓守长。 目录 😈1. 初识…...

JVM基础扫盲
什么是JVM JVM是Java设计者用于屏蔽多平台差异,基于操作系统之上的一个"小型虚拟机",正是因为JVM的存在,使得Java应用程序运行时不需要关注底层操作系统的差异。使得Java程序编译只需编译一次,在任何操作系统都可以以相…...

SpringBoot基于gRPC进行RPC调用
SpringBoot基于gRPC进行RPC调用 一、gRPC1.1 什么是gRPC?1.2 如何编写proto1.3 数据类型及对应关系1.4 枚举1.5 数组1.6 map类型1.7 嵌套对象 二、SpringBoot gRPC2.1 工程目录2.2 jrpc-api2.2.1 引入gRPC依赖2.2.2 编写 .proto 文件2.2.3 使用插件机制生产proto相关…...

浏览器的事件循环机制(Event loop)
事件循环 浏览器的进程模型 何为进程? 程序运行需要有它自己专属的内存空间,可以把这块内存空间简单的理解为进程 每个应用至少有一个进程,进程之间相互独立,即使要通信,也需要双方同意。 何为线程? …...

THEMIS---Beta Sprint Summary Essay Blog
Which course does this assignment belong to2301-MUSE社区-CSDN社区云What are the requirements for this assignmentbeta SprintThe goal of this assignmentTo summarize the beta task progress and the teams sprintsTeam NameThemisTop-of-the-line collection of essa…...

Vue中实现分布式动态路由的基本实现步骤介绍
设想一下,我们在做一个体量非常大的项目,这个项目有很多的模块和相当多的页面。当我们想修改一个路由的时候,我们打开了router文件夹下的index.js文件时,一串长到鼠标滚轮需要滚大半天才滚到底的路由简直让人头皮发麻。 在开始之前…...