当前位置： 首页 > news >正文

【数据结构】什么是堆?

news 2025/9/14 6:54:46

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

堆的概念及结构

堆的定义如下:

n个元素的序列{k1,k2,...,kn}当且仅当满足以下关系时,称之为堆.

 \left\{\begin{matrix} k_{i}\geqslant k_{2i} \\ k_{i}\geqslant k_{2i+1} & & \end{matrix}\right.    或    \left\{\begin{matrix} k_{i}\leqslant k_{2i} \\ k_{i}\leqslant k_{2i+1} & & \end{matrix}\right.

(i= 1,2,...,\left \lfloor \frac{n}{2} \right \rfloor)

把这个序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有双亲结点的值均不小于(或不大于)其左,右孩子结点的值.

由此,若序列 {k1,k2,...,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最大值(或最小值).

如下面两个序列为堆(存储结构),则其对应的完全二叉树(逻辑结构)如下图所示:

综上,我们不难总结出堆的性质:

  • 堆中某个结点的值总是不大于或不小于其父亲结点的值.
  • 堆总是一颗完全二叉树.

堆的实现

有关堆结构的完整实现部分我放在下面这篇博客中为大家详细梳理了,并且为每个算法逻辑配备了详细明了的逻辑结构演示图和物理结构演示图,如:

对堆的实现部分的具体逻辑和细节感兴趣的朋友可以点击下方链接直接跳转到相应文章:

【数据结构】C语言实现堆(附完整运行代码)icon-default.png?t=N7T8http://t.csdnimg.cn/v7qVo

建堆的时间复杂度

建堆有两种方式,一种是从堆顶开始向下建堆,另一种是从堆尾开始向上建堆.乍一听好像两种建堆方式除了向上调整和向下调整方式不同之外没什么区别,但我们仔细分析一下,其实这两种建堆方式的时间复杂度差别是很大的.

向上调整建堆

我们先一起来分析一下向上建堆的时间复杂度:

首先,按照算法算法最坏时间复杂度分析,我们假设堆是完全二叉树中的满二叉树,并且假设每个结点的移动次数都是最坏移动次数,则:

使用错位相消法,可得:

化简,可得:

使用大O阶渐近表示法,可得:

T(n) = 2^h*h = O(n*log_{2}n)

因为:

2^h=n

h=log_{2}n

(舍去低次方阶和常数阶后剩下的2^h恰好是高为h的树的结点个数n,同样的h也可化简为以2为底n的对数)

向下调整建堆

再来看看向下调整建堆:

我们继续,按照算法最坏时间复杂度分析,假设堆是完全二叉树中的满二叉树,并且假设每个结点的移动次数都是最坏移动次数,则:

使用错位相消法,可得T(n)为:

化简,可得:

使用大O阶渐近表示法,可得:

T(n) = 2^h = O(n)

(舍去低次方阶和常数阶后剩下的2^h恰好是高为h的树的结点个数n)

综上可知:

  • 向上调整的建堆方式的时间复杂度为O(n*log_{2}n)
  • 向下调整的建堆方式的时间复杂度为O(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}当且仅当满足以下关系时,称之为堆. 或 把这个序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个…...

编程日记 2023/12/18 19:36:54

生产环境_Spark处理轨迹中跨越本初子午线的经度列

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

编程日记 2023/12/18 19:33:50

Vue前端与后端放在一起的搭建方式

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

编程日记 2023/12/18 19:31:48

SI24R03国产自主可控RISC-V架构MCU低功耗2.4GHz收发芯片SoC

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

编程日记 2023/12/18 19:30:47

基于FPGA的温度控制系统设计（论文+源码）

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

编程日记 2023/12/18 19:27:43

C语言训练：三个字符串比较大小，实现两个整数数的交换统计二进制中1的个数

目录 一、编写程序，输入三个字符串，比较它们的大小，并将它们按由小到大的顺序输出。要求用函数、指针实现。要求:要采用函数调用，并用指向函数的指针作为函数的参数。 1.不使用函数指针作为参数，并自己模拟strcmp。 …...

编程日记 2023/12/18 19:26:42

module ‘tensorflow‘ has no attribute XXX 报错解决

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

编程日记 2023/12/18 19:23:40

MySQL数据库 DDL

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

编程日记 2023/12/18 19:21:38

力扣二叉树--总结篇（2）

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

编程日记 2023/12/18 19:20: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…...

编程日记 2023/12/18 19:19:37

从零开始创建一个项目，springBoot+mybatisPlus+mysql+swagger+maven

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

编程日记 2023/12/18 19:17:35

【视点合成】代码解读：生成demo视频

变换工具 def render_3dphoto(src_imgs, # 输入的源图像&#xff0c;维度为 [batch_size, 3, height, width]mpi_all_src, # 输入的所有源图像的MPI&#xff0c;维度为 [batch_size, num_planes, 4, height, width]disparity_all_src, # 所有源图像的视差信息&…...

编程日记 2023/12/18 19:13:31

Process On在线绘制流程图

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

编程日记 2023/12/18 19:09:27

【Hadoop-OBS-Hive】利用华为云存储对象 OBS 作为两个集群的中间栈 load 文件到 Hive

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

编程日记 2023/12/18 19:06:24

直线检测算子

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

编程日记 2023/12/18 19:05:23

如何在本地Docker中部署MinIO服务并实现远程访问管理界面

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

编程日记 2023/12/18 19:04:22

逛商场。。。

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

编程日记 2023/12/18 19:02:20

RTrPPG

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

编程日记 2023/12/18 18:58:16

web应用开发技术的一些概念

一、Servlet 1.Servlet的工作过程&#xff1a; Servelt的工作流程示意图 &#xff08;1&#xff09;客户端发起一个Http请求到服务器&#xff0c;请求特定的资源或者是要执行特定的操作 &#xff08;2&#xff09;服务器在接收到请求后&#xff0c;根据请求相应的URL将请求分发…...

编程日记 2023/12/18 18:50:09

智能优化算法应用：基于乌燕鸥算法3D无线传感器网络(WSN)覆盖优化 - 附代码

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

编程日记 2023/12/18 18:48:07

19c补丁后oracle属主变化，导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

编程新知 2025/9/14 3:07:02

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

编程新知 2025/9/9 10:11:34

工业自动化时代的精准装配革新：迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

编程新知 2025/7/18 2:05:01

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

编程新知 2025/8/26 22:28:46

【HarmonyOS 5 开发速记】如何获取用户信息（头像/昵称/手机号）

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

编程新知 2025/7/17 1:57:52

iOS性能调优实战：借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

编程新知 2025/8/11 22:22:05

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

编程新知 2025/7/6 7:40:12

TSN交换机正在重构工业网络，PROFINET和EtherCAT会被取代吗？

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

编程新知 2025/9/6 22:13:40

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

编程新知 2025/9/13 17:32:59

网页端 js 读取发票里的二维码信息（图片和PDF格式）

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...

编程新知 2025/9/13 0:08:42