当前位置: 首页 > 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;需要根据实验目的、实验原理、实…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...