【数据结构】什么是堆?
🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境: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.参考文…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...
在Zenodo下载文件 用到googlecolab googledrive
方法:Figshare/Zenodo上的数据/文件下载不下来?尝试利用Google Colab :https://zhuanlan.zhihu.com/p/1898503078782674027 参考: 通过Colab&谷歌云下载Figshare数据,超级实用!!࿰…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...





















