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

【数据结构】什么是堆?

news 2025/7/2 18:20:36

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境: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

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

编程新知 2025/7/1 23:49:53

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

编程新知 2025/6/17 2:24:14

在Ubuntu中设置开机自动运行（sudo）指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

编程新知 2025/6/18 4:00:59

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

编程新知 2025/6/17 3:05:21

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

编程新知 2025/6/21 14:07:25

如何在最短时间内提升打ctf（web)的水平？

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

编程新知 2025/6/23 2:47:18

云原生玩法三问：构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

编程新知 2025/6/21 14:21:20

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/6/17 23:45:45

数据结构：递归的种类（Types of Recursion）

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

编程新知 2025/6/28 13:59:37

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...

编程新知 2025/6/21 10:57:07