二叉树与堆相关的时间复杂度问题
目录
满二叉树与完全二叉树高度h和树中节点个数N的关系
向上调整算法:
介绍:
复杂度推导:
向下调整算法:
介绍:
复杂度推导:
向上调整建堆:
介绍:
复杂度推导:
向下调整建堆:
介绍:
复杂度推导:
满二叉树与完全二叉树高度h和树中节点个数N的关系
向上调整算法:
介绍:
函数功能:将堆通过向上调整算法使堆成为小堆(父亲<孩子)或大堆(父亲>孩子),堆内父亲=(孩子-1)/2。只要孩子还在堆范围内,就不断判断孩子与父亲的关系。若想设置小堆,则孩子<父亲就执行交换;若想设置大堆,则孩子>父亲就执行交换。
函数参数:HeapDataType * a—>堆内数据类型首元素的指针 int child—>堆底元素(孩子)
函数返回值:无
void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
复杂度推导:
一次向上调整最多调整高度次数,根据满二叉树h=log(N+1),完全二叉树h=log(N)+1,而时间复杂度计算的是最大情况的数量级,所以一次向上调整的复杂度为O(logN)
向下调整算法:
介绍:
函数功能:将堆通过向下调整算法使堆成为小堆(父亲<孩子)或大堆(父亲>孩子),使用假设法先假定要交换的元素为左孩子,child=parent*2+1,若右孩子>左孩子,则需交换的元素为parent*2+1+1。只要孩子还在堆范围内,就不断判断孩子与父亲的关系。若想设置小堆,则孩子<父亲就执行交换;若想设置大堆,则孩子>父亲就执行交换。
函数参数:HeapDataType * a—>堆内数据类型首元素的指针 int n —>堆内元素个数 int parent—>堆顶元素(父亲)
函数返回值:无
void Adjustdown(HeapDataType* a, int n, int parent)
{size_t child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
复杂度推导:
一次向下调整最多调整高度次数,根据满二叉树h=log(N+1),完全二叉树h=log(N)+1,而时间复杂度计算的是最大情况的数量级,所以一次向下调整的复杂度为O(logN)
向上调整建堆:
介绍:
前提:上几层都是堆
先将数组内所有元素插入堆结构内,再从第一个元素到最后一个元素进行遍历,对每个元素使用向上调整算法,使堆结构成为大堆/小堆
复杂度推导:
向下调整建堆:
介绍:
前提:左右子树都是堆
先将数组内所有元素插入堆结构内,再从最后一个父亲的位置到第一个父亲的位置进行遍历,对每个元素使用向下调整算法,使堆结构成为大堆/小堆
复杂度推导:
相关文章:

二叉树与堆相关的时间复杂度问题
目录 满二叉树与完全二叉树高度h和树中节点个数N的关系 向上调整算法: 介绍: 复杂度推导: 向下调整算法: 介绍: 复杂度推导: 向上调整建堆: 介绍: 复杂度推导:…...

goLang小案例-获取从控制台输入的信息
goLang小案例-获取从控制台输入的信息 1. 案例代码展示 package mainimport ("bufio""fmt""log""os" )var pl fmt.Printlnfunc main() {//控制台输出欢迎提示pl("Hello Go")fmt.Print("what is your name? ")…...

1-5题查询 - 高频 SQL 50 题基础版
目录 1. 相关知识点2. 例题2.1.可回收且低脂的产品2.2.寻找用户推荐人2.3.大的国家2.4. 文章浏览 I2.5. 无效的推文 1. 相关知识点 sql判断,不包含null,判断不出来distinct是通过查询的结果来去除重复记录ASC升序计算字符长度 CHAR_LENGTH() 或 LENGTH(…...

Modbus协议转Profinet协议网关模块连智能仪表与PLC通讯
一、现场需求:PLC作为控制器,仪表设备做为执行设备,执行设备能够实时响应PLC传来的指令,并且向PLC回馈数据,从而达到PLC对仪表设备进行控制和监测,实现对生产过程的精准控制。 二、解决方案:通过…...

新手必学:TikTok视频标签的使用方法
想让你的TikTok视频火起来,就得用对标签。标签能帮你的作品被更多人看到,也更有利于推广,可以为品牌增加曝光度、吸引更多观众、提高转化率和借势热门话题。那么应该如何选择标签并使用标签呢,看完这篇分享你或许会有所启发&#…...
AI是在帮助开发者还是取代他们
近年来,AI工具在软件开发和数据分析领域的应用日益广泛,它们对开发者的日常工作产生了深远的影响。AI工具通过自动化处理大量数据、优化代码质量、提高测试效率等方式,极大地提升了开发者的工作效率。然而,这同时也对开发者的传统…...

【后端面试题】【中间件】【NoSQL】MongoDB查询过程、ESR规则、覆盖索引的优化
任何中间件的面试说到底都是以高可用、高性能和高并发为主,而高性能和高并发基本是同时存在的。 性能优化一直被看作一个高级面试点,因为只有对原理了解得很透彻的人,在实践中才能找准性能优化的关键点,从而通过各种优化手段解决性…...
使用c++函数式编程实现Qt信号槽机制
问题背景 在下面的代码中,Input输入器 输入数据,希望A和B 接收数据。但使用的赋值,导致in.a和a只是拷贝数据,而不是同一个对象,使得数据不同步。 #include <iostream> struct A {int age 32; }; struct B {int …...
【Android】Activity子类之间的区别
从底层往顶层的继承顺序依次是: Activity,最原始的Activity androidx.core.app.ComponentActivity,仅仅优化了一个关于KeyEvent的拦截问题,一般不继承这个类 androidx.activity.ComponentActivity,支持和Android Arc…...

在 Mac 上使用 MLX 微调微软 phi3 模型
微调大语言模型是常见的需求,由于模型参数量大,即使用 Lora/Qlora 进行微调也需要 GPU 显卡,Mac M系是苹果自己的 GPU,目前主流的框架还在建立在 CUDA 的显卡架构,也就是主要的卡还是来自英伟达。如果要用 Mac 来做训练…...

【JavaEE】多线程代码案例(2)
🎏🎏🎏个人主页🎏🎏🎏 🎏🎏🎏JavaEE专栏🎏🎏🎏 🎏🎏🎏上一篇文章:多线程代码案例(1)&a…...

Halcon支持向量机
一 支持向量机 1 支持向量机介绍: 支持向量机(Support Vector Machine,SVM)是Corinna Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别表现出许多特有的优势。 2 支持向量机原理: 在n维空间中找到一个分类超平面…...
【Python机器学习】模型评估与改进——在模型选择中使用评估指标
我们通常希望,在使用GridSearchCV或cross_val_score进行模型选择时能够使用AUC等指标。scikit-learn提供了一种非常简单的实现方法,那就是scoring参数,它可以同时用于GridSearchCV和cross_val_score。你只需要提供一个字符串,用于…...

【C语言】union 关键字
在C语言中,union关键字用于定义联合体。联合体是一种特殊的数据结构,它允许不同的数据类型共享同一段内存。所有联合体成员共享同一个内存位置,因此联合体的大小取决于其最大成员的大小。 定义和使用联合体 基本定义 定义一个联合体类型时…...

电脑回收站删除的文件怎么恢复?5个恢复方法详解汇总!
电脑回收站删除的文件怎么恢复?在我们日常使用电脑的过程中,难免会遇到误删文件的情况。一旦发现自己误删文件了,先不要着急,还是有很多方法可以找回的。市面上还是有很多好用的文件恢复软件可以使用,具体介绍如下。 本…...
mac 安装cnpm 淘宝镜像记录
mac 安装cnpm 淘宝镜像记录 本文介绍了在安装cnpm时遇到权限问题的解决方案,包括使用sudo,处理SSL证书过期,以及因版本不一致导致的错误处理方法,步骤包括设置npm配置、卸载和重新安装cnpm到特定版本。 安装 npm install cnpm …...
ArcGIS Pro SDK (七)编辑 11 撤销重做
ArcGIS Pro SDK (七)编辑 11 撤销&重做 文章目录 ArcGIS Pro SDK (七)编辑 11 撤销&重做1 撤消/重做最近的操作 环境:Visual Studio 2022 .NET6 ArcGIS Pro SDK 3.0 1 撤消/重做最近的操作 //撤销 if (MapV…...
Excel 中的元素定位:相对定位、绝对定位和混合定位
在Excel中,单元格引用有三种主要类型:相对定位、绝对定位和混合定位。 这些类型主要用于公式和函数中,决定在复制或拖动公式时引用如何变化。 1. 相对定位 相对定位指的是不带“$”符号的单元格引用,例如 A1。 这种引用方式在…...
Idea2024安装后点击无响应
问题 最近因工作需要,升级一下 idea 版本,之前一直使用的是2020版本,下载最新的2024版本(下载的 zip 包免安装模式,之前使用的2020版本也是免安装的,因为是免安装的,所以之前的版本也没有删除&…...
如何提高实验室分析结果的准确性呢
要提高实验室分析结果的准确性,可以从以下几个方面着手: 1、选择合适的实验方法 不同的实验方法具有不同的优缺点,实验方法的准确度直接影响测定结果的准确度。因此,在选择实验方法时,需要根据实验目的、实验原理、实…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...