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

二叉树与堆相关的时间复杂度问题

目录

满二叉树与完全二叉树高度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的关系 向上调整算法&#xff1a; 介绍&#xff1a; 复杂度推导&#xff1a; 向下调整算法&#xff1a; 介绍&#xff1a; 复杂度推导&#xff1a; 向上调整建堆&#xff1a; 介绍&#xff1a; 复杂度推导&#xff1a;…...

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判断&#xff0c;不包含null&#xff0c;判断不出来distinct是通过查询的结果来去除重复记录ASC升序计算字符长度 CHAR_LENGTH() 或 LENGTH(…...

Modbus协议转Profinet协议网关模块连智能仪表与PLC通讯

一、现场需求&#xff1a;PLC作为控制器&#xff0c;仪表设备做为执行设备&#xff0c;执行设备能够实时响应PLC传来的指令&#xff0c;并且向PLC回馈数据&#xff0c;从而达到PLC对仪表设备进行控制和监测&#xff0c;实现对生产过程的精准控制。 二、解决方案&#xff1a;通过…...

新手必学:TikTok视频标签的使用方法

想让你的TikTok视频火起来&#xff0c;就得用对标签。标签能帮你的作品被更多人看到&#xff0c;也更有利于推广&#xff0c;可以为品牌增加曝光度、吸引更多观众、提高转化率和借势热门话题。那么应该如何选择标签并使用标签呢&#xff0c;看完这篇分享你或许会有所启发&#…...

AI是在帮助开发者还是取代他们

近年来&#xff0c;AI工具在软件开发和数据分析领域的应用日益广泛&#xff0c;它们对开发者的日常工作产生了深远的影响。AI工具通过自动化处理大量数据、优化代码质量、提高测试效率等方式&#xff0c;极大地提升了开发者的工作效率。然而&#xff0c;这同时也对开发者的传统…...

【后端面试题】【中间件】【NoSQL】MongoDB查询过程、ESR规则、覆盖索引的优化

任何中间件的面试说到底都是以高可用、高性能和高并发为主&#xff0c;而高性能和高并发基本是同时存在的。 性能优化一直被看作一个高级面试点&#xff0c;因为只有对原理了解得很透彻的人&#xff0c;在实践中才能找准性能优化的关键点&#xff0c;从而通过各种优化手段解决性…...

使用c++函数式编程实现Qt信号槽机制

问题背景 在下面的代码中&#xff0c;Input输入器 输入数据&#xff0c;希望A和B 接收数据。但使用的赋值&#xff0c;导致in.a和a只是拷贝数据&#xff0c;而不是同一个对象&#xff0c;使得数据不同步。 #include <iostream> struct A {int age 32; }; struct B {int …...

【Android】Activity子类之间的区别

从底层往顶层的继承顺序依次是&#xff1a; Activity&#xff0c;最原始的Activity androidx.core.app.ComponentActivity&#xff0c;仅仅优化了一个关于KeyEvent的拦截问题&#xff0c;一般不继承这个类 androidx.activity.ComponentActivity&#xff0c;支持和Android Arc…...

在 Mac 上使用 MLX 微调微软 phi3 模型

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

【JavaEE】多线程代码案例(2)

&#x1f38f;&#x1f38f;&#x1f38f;个人主页&#x1f38f;&#x1f38f;&#x1f38f; &#x1f38f;&#x1f38f;&#x1f38f;JavaEE专栏&#x1f38f;&#x1f38f;&#x1f38f; &#x1f38f;&#x1f38f;&#x1f38f;上一篇文章&#xff1a;多线程代码案例(1)&a…...

Halcon支持向量机

一 支持向量机 1 支持向量机介绍&#xff1a; 支持向量机(Support Vector Machine&#xff0c;SVM)是Corinna Cortes和Vapnik于1995年首先提出的&#xff0c;它在解决小样本、非线性及高维模式识别表现出许多特有的优势。 2 支持向量机原理: 在n维空间中找到一个分类超平面…...

【Python机器学习】模型评估与改进——在模型选择中使用评估指标

我们通常希望&#xff0c;在使用GridSearchCV或cross_val_score进行模型选择时能够使用AUC等指标。scikit-learn提供了一种非常简单的实现方法&#xff0c;那就是scoring参数&#xff0c;它可以同时用于GridSearchCV和cross_val_score。你只需要提供一个字符串&#xff0c;用于…...

【C语言】union 关键字

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

电脑回收站删除的文件怎么恢复?5个恢复方法详解汇总!

电脑回收站删除的文件怎么恢复&#xff1f;在我们日常使用电脑的过程中&#xff0c;难免会遇到误删文件的情况。一旦发现自己误删文件了&#xff0c;先不要着急&#xff0c;还是有很多方法可以找回的。市面上还是有很多好用的文件恢复软件可以使用&#xff0c;具体介绍如下。 本…...

mac 安装cnpm 淘宝镜像记录

mac 安装cnpm 淘宝镜像记录 本文介绍了在安装cnpm时遇到权限问题的解决方案&#xff0c;包括使用sudo&#xff0c;处理SSL证书过期&#xff0c;以及因版本不一致导致的错误处理方法&#xff0c;步骤包括设置npm配置、卸载和重新安装cnpm到特定版本。 安装 npm install cnpm …...

ArcGIS Pro SDK (七)编辑 11 撤销重做

ArcGIS Pro SDK &#xff08;七&#xff09;编辑 11 撤销&重做 文章目录 ArcGIS Pro SDK &#xff08;七&#xff09;编辑 11 撤销&重做1 撤消/重做最近的操作 环境&#xff1a;Visual Studio 2022 .NET6 ArcGIS Pro SDK 3.0 1 撤消/重做最近的操作 //撤销 if (MapV…...

Excel 中的元素定位:相对定位、绝对定位和混合定位

在Excel中&#xff0c;单元格引用有三种主要类型&#xff1a;相对定位、绝对定位和混合定位。 这些类型主要用于公式和函数中&#xff0c;决定在复制或拖动公式时引用如何变化。 1. 相对定位 相对定位指的是不带“$”符号的单元格引用&#xff0c;例如 A1。 这种引用方式在…...

Idea2024安装后点击无响应

问题 最近因工作需要&#xff0c;升级一下 idea 版本&#xff0c;之前一直使用的是2020版本&#xff0c;下载最新的2024版本&#xff08;下载的 zip 包免安装模式&#xff0c;之前使用的2020版本也是免安装的&#xff0c;因为是免安装的&#xff0c;所以之前的版本也没有删除&…...

如何提高实验室分析结果的准确性呢

要提高实验室分析结果的准确性&#xff0c;可以从以下几个方面着手&#xff1a; 1、选择合适的实验方法 不同的实验方法具有不同的优缺点&#xff0c;实验方法的准确度直接影响测定结果的准确度。因此&#xff0c;在选择实验方法时&#xff0c;需要根据实验目的、实验原理、实…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...