数据结构 ——— 向上调整建堆和向下调整建堆的区别

目录

前言

向下调整算法(默认小堆)

利用向下调整算法对数组建堆

向上调整建堆和向下调整建堆的区别​编辑

向下调整建堆的时间复杂度:

向上调整建堆的时间复杂度:

结论 


前言

在上一章讲解到了利用向上调整算法对数组进行建堆
再利用首尾交换和向下调整建堆算法对数组调整成升序或者降序

数据结构 ——— 向上/向下调整算法将数组调整为升/降序-CSDN博客

接下来要学习的是:利用向下调整算法建堆,然后再比较区别


向下调整算法(默认小堆)

static void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 先找到左右孩子中小的那个if ((child + 1 < size) && (a[child + 1] < a[child]))child++;if (a[parent] > a[child]){// 交换Swap(&a[parent], &a[child]);// 迭代parent = child;child = parent * 2 + 1;}else{break;}}
}

推理过程已经在上一章讲解了,这里就不过多赘述


利用向下调整算法对数组建堆

有以下整型数组a:

int a[] = { 5,7,3,9,1,8,4,6,2 };

如何利用向下调整算法对数组建堆呢?

使用向下调整算法的前提是:需要向下调整的数据的左右子树都是堆,才能使用向下调整算法,否则就算使用向下调整算法,也不能建堆
现在的主要问题就是数组 a 不是堆,且数组首元素的左右子树也不是堆

解决办法:

从数组最后一个元素开始往前向下调整建堆
因为向下建堆的前提是要左右子树是一个堆,那么就先把左右子树建堆,左右子树中又会有左右子树,直到根节点,就停止建堆
所以只需要从数组最后一个元素开始往前依次利用向下建堆算法进行建堆,那么就能把数组 a 建立成大堆/小堆
但是必须要从数组的最后一个元素开始建堆吗?
其实不用,因为最后一个元素是叶子节点,叶子节点的特点就是没有孩子节点,那么叶子节点本身就是一个堆

           5

        /      \
     7          3
    /  \        /  \
  9   1      8  4

 / \
6 2

6、2、8、4 都属于叶子节点,那么就不用对这些节点进行向下调整算法
那么只需要从最后一个叶子节点的父亲节点开始往前进行向下调整算法 
假设最后一个叶子节点 2 的下标为 child
那么父亲节点就可以通过 (child-1)/2 这个公式进行计算,2 的父亲节点也就是 9
对 9 进行了向下调整算法后,就需要对 3 这个子树进行向下调整算法
而且找 3 这个节点只需要 9 节点的下标减一即可
依次往前向下调整,最后调整到数组的首元素,那么就完成了对数组 a 进行建堆

代码验证:

           1

        /      \
     2          3
    /  \        /  \
  5   7      8  4

 / \
6 9


向上调整建堆和向下调整建堆的区别

向下调整建堆的时间复杂度:

最后一层是叶子节点,所以不需要使用向下调整算法
从倒数第二层开始,使用向下调整算法进行建堆
倒数第二层有 2^(h-2) 个节点,每个节点最多向下调整 1 次
那么倒数第二层一共向下调整 2^(h-2)*1 次
倒数第三层有 2^(h-3) 个节点,每个节点最多向下调整 2 次
那么倒数第三层一共向下调整 2^(h-2)*2 次
………………
第二层有 2^1 个节点,每个节点最多向下调整 h-2 次
那么第二层一共向下调整 2^1*(h-2) 次
第二层有 2^0 个节点,每个节点最多向下调整 h-1 次
那么第一层一共向下调整 2^0*(h-1) 次

得出时间复杂度表达式:
F(h) = 2^(h-2)*1 + 2^(h-3)*2 + …… + 2^1*(h-2) + 2^0*(h-1)

通过错位相减法简化以上公式得出:
F(h) = 2^h - 1 - h

且假设节点的总个数为 N ,那么高度h和节点N的关系是: 2^h - 1 == N

最后得出向下调整建堆整体复杂度为:
F(N) = N - log(N+1)
大O渐进表示法:O(N) ,(log(N+1)可以忽略不计)

向上调整建堆的时间复杂度:

除了根节点,其他节点都需要使用向上调整算法
第二层有 2^1 个节点,每个节点最多向上调整 1 次
那么第二层一共向上调整 2^1*1 次
………………
最后一层有 2^(h-1) 个节点,每个节点最多向上调整 (h-1) 次
那么最后一层一共向上调整 2^(h-1)*(h-1) 次

得出时间复杂度表达式:
F(h) = 2^1*1 + 2^2*2 + …… + 2^(h-2)*(h-2) + 2^(h-1)*(h-1)

通过错位相减法简化以上公式得出:
F(h) = 2^h*(h-2)+2

且假设节点的总个数为 N ,那么高度h和节点N的关系是: 2^h - 1 == N

最后得出向下调整建堆整体复杂度为:
F(N) = (N+1) * (log(N+1)-2) + 2
大O渐进表示法:O(N*longN)

结论

向下调整算法的时间复杂度低于向上调整算法的时间复杂度
那么也就是向下调整算法的效率高于向上调整算法的效率

所以要对数组进行建堆的话,推荐使用向下调整建堆算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/461616.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分享几款开源好用的图片在线编辑,适合做快速应用嵌入

图片生成器是指一种工具或软件&#xff0c;用于自动生成图片或图像内容&#xff0c;通常依据用户设定的参数或模板进行操作。这种工具能够帮助用户快速创建视觉效果丰富的图像&#xff0c;而无需具备专业的设计技能。 在数字化时代&#xff0c;图片编辑已经成为日常工作和生活的…

我为何要用wordpress搭建一个自己的独立博客

我在csdn有一个博客&#xff0c;这个博客是之前学习编程时建立的。 博客有哪些好处呢&#xff1f; 1&#xff0c;可以写自己的遇到的问题和如何解决的步骤 2&#xff0c;心得体会&#xff0c;经验&#xff0c;和踩坑 3&#xff0c;可以转载别人的好的技术知识 4&#xff0c;宝贵…

ts:使用fs内置模块简单读写文件

ts&#xff1a;使用fs内置模块简单读写文件 一、主要内容说明二、例子&#xff08;一&#xff09;、fs模块的文件读写1.源码1 &#xff08;fs模块的文件读写&#xff09;2.源码1运行效果 三、结语四、定位日期 一、主要内容说明 在ts中&#xff0c;我们可以使用内置的fs模块来…

十个常见的软件测试面试题,拿走不谢

所有面试问题一般建议先总后分的方式来回答&#xff0c;这样可以让面试官感觉逻辑性很强。 1. 自我介绍 之所以让我们自我介绍&#xff0c;其实是面试官想找一些时间来看简历&#xff0c;所以自我介绍不用太长的时间&#xff0c;1-2分 钟即可。 自我介绍一般按以下方式进行介…

C++中关于 <functional> 的使用

#include <functional> 是 C 标准库中的一个头文件&#xff0c;主要用于提供与函数对象、函数指针和函数适配器相关的功能 一&#xff1a;定义方式 1. 定义和使用 std::function 和 Lambda 表达式 2&#xff1a;使用 std::bind 你可以使用 std::bind 来绑定函数参数&am…

Axios 请求超时设置无效的问题及解决方案

文章目录 Axios 请求超时设置无效的问题及解决方案1. 引言2. 理解 Axios 的超时机制2.1 Axios 超时的工作原理2.2 超时错误的处理 3. Axios 请求超时设置无效的常见原因3.1 配置错误或遗漏3.2 超时发生在建立连接之前3.3 使用了不支持的传输协议3.4 代理服务器或中间件干扰3.5 …

WPF+MVVM案例实战(十五)- 实现一个下拉式菜单(上)

文章目录 1 案例效果2、图标资源下载3、功能实现1.文件创建2、菜单原理分析3、一级菜单两种样式实现1、一级菜单无子项样式实现2、一级菜单有子项样式实现 4、总结 1 案例效果 提示 2、图标资源下载 从阿里矢量素材官网下载需要的菜单图片&#xff0c;如下所示&#xff1a; …

【环境搭建】Apache ZooKeeper 3.8.4 Stable

软件环境 Ubuntu 20.04 、OpenJDK 11 OpenJDK 11&#xff08;如果已经安装&#xff0c;可以跳过这一步&#xff09; 安装OpenJDK 11&#xff1a; $ sudo apt-get update$ sudo apt-get install -y openjdk-11-jdk 设置 JAVA_HOME 环境变量&#xff1a; $ sudo gedit ~/.bash…

后台管理系统的通用权限解决方案(九)SpringBoot整合jjwt实现登录认证鉴权

1&#xff09;创建maven工程jjwt-login-demo&#xff0c;并配置其pom.xml文件如下 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-ins…

国考报名照片无法使用照片审核工具上传失败的解决办法

国考报名过程中&#xff0c;照片审核是至关重要的一步&#xff0c;但许多考生在上传照片时遇到了难题&#xff0c;导致无法继续报名&#xff0c;从而影响抢考场位置&#xff0c;下面就介绍如何快速完成照片处理、审核和上传过审的技巧。 一、国考报名照片基本要求首先&#xff…

vue中如何为不同功能设置不同的默认打印设置(设置不同的打印机)

浏览器自带的window.print 功能较简单&#xff0c;这里使用LODOP露肚皮打印 以下是vue2示例&#xff1a; 从官网中下载Lodop和C-Lodop官网主站安装包并安装到本地电脑可以全局搜索电脑找到安装文件LodopFuncs.js&#xff0c;也可以直接复制我贴出来的文件 //用双端口加载主JS…

数据库管理系统的ACID都各自是什么?

本文基于DBMS中ACID属性的概念&#xff0c;这些属性保证了数据库中执行事务时保持数据一致性、完整性和可靠性所。事务是访问并可能修改数据库内容的单一逻辑工作单元。交易使用读写操作访问数据。为了保持数据库的一致性&#xff0c;在事务前后&#xff0c;遵循某些属性。这些…

ssm基于vue搭建的新闻网站+vue

系统包含&#xff1a;源码论文 所用技术&#xff1a;SpringBootVueSSMMybatisMysql 免费提供给大家参考或者学习&#xff0c;获取源码请私聊我 需要定制请私聊 目 录 目 录 I 摘 要 III ABSTRACT IV 1 绪论 1 1.1 课题背景 1 1.2 研究现状 1 1.3 研究内容 2 [2 系统…

OB_GINS_day3

这里写目录标题 实现当前状态初始化实现预积分的初始化由于此时preintegration_options 是3&#xff08;也就是考虑odo以及earth rotation&#xff09;为预积分的容器添加需要积分的IMU积分因子接下来是添加新的IMU到preintegration中 实现当前状态初始化 这个state_curr的主要…

如何优化kafka和mysql处理百万级消息计算和落库

一.业务场景 最近业务需要&#xff0c;做了性能优化操作。百万级消息在kafka中秒级传输。cpu密集计算分钟级完成&#xff0c;然后在mysql中秒级落库.模型cpu计算提高了1倍&#xff0c;落表速度提高了5倍&#xff0c;2分钟内完成. 如下序列图&#xff1a; 业务系统A发送千级别…

深度学习基础知识-Batch Normalization(BN)超详细解析

一、背景和问题定义 在深层神经网络&#xff08;Deep Neural Networks, DNNs&#xff09;中&#xff0c;层与层之间的输入分布会随着参数更新不断发生变化&#xff0c;这种现象被称为内部协变量偏移&#xff08;Internal Covariate Shift&#xff09;。具体来说&#xff0c;由…

NLP算法工程师精进之路:顶会论文研读精华

1.学术能力培养 全部论文资料下载&#xff1a; 将论文和 GitHub 资源库匹配 papers with code https://paperswithcode.com/OpenGitHub 新项目快报Github pwc&#xff1a;https://github.com/zziz/pwc GitXiv&#xff1a;http://www.gitxiv.com/ 文章撰写 Overleaf [Autho…

从倍压整流到二极管钳位与限幅

何为倍压整流&#xff1f;这里直接引用“百度百科”解释&#xff0c;如下述。 在一些需用高电压、小电流的地方&#xff0c;常常使用倍压整流电路。倍压整流&#xff0c;可以把较低的交流电压&#xff0c;用耐压较高的整流二极管和电容器&#xff0c;“整”出一个较高的直流电…

Java项目实战II基于Java+Spring Boot+MySQL的工程教育认证的计算机课程管理平台(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 随着工程教…

uniapp开发小程序【简单的实现点击下拉选择性别功能】

一、展示效果 二、代码 <template><view><view class="form_box"><view class="item"