二叉树与堆相关的时间复杂度问题
目录
满二叉树与完全二叉树高度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、选择合适的实验方法 不同的实验方法具有不同的优缺点,实验方法的准确度直接影响测定结果的准确度。因此,在选择实验方法时,需要根据实验目的、实验原理、实…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
