二叉树与堆相关的时间复杂度问题
目录
满二叉树与完全二叉树高度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、选择合适的实验方法 不同的实验方法具有不同的优缺点,实验方法的准确度直接影响测定结果的准确度。因此,在选择实验方法时,需要根据实验目的、实验原理、实…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
