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

三十岁想从零转行现实吗?带你分辨真正有前景的好工作

![](https://img-blog.csdnimg.cn/direct/b0bfa28b59f9478dae4e6feee6659cce.png)我是29岁那年&#xff0c;完成从转行裸辞副业的职业转型。 如果你把职业生涯看成是从现在开始30岁&#xff0c;到你退休那年&#xff0c;中间这么漫长的30年&#xff0c;那么30岁转行完全来得及…...

美团外卖mtgsig与waimai_sign双层签名逆向解析

1. 这不是“爬虫教程”&#xff0c;而是一份反向工程现场笔记你搜到这篇内容&#xff0c;大概率正卡在某个调试窗口前&#xff1a;抓包看到mtgsig和waimai_sign两个参数像两堵墙&#xff0c;无论怎么改请求头、换UA、清缓存&#xff0c;返回永远是{"code":403,"…...

如何快速解锁艾尔登法环帧率限制:终极性能优化指南

如何快速解锁艾尔登法环帧率限制&#xff1a;终极性能优化指南 【免费下载链接】EldenRingFpsUnlockAndMore A small utility to remove frame rate limit, change FOV, add widescreen support and more for Elden Ring 项目地址: https://gitcode.com/gh_mirrors/el/EldenR…...

解决方法:庐山派K230接串口没识别到端口问题

一、插入usb转串口工具之前二、插入usb转串口工具之后三、解决方法说明&#xff1a;&#x1f50d; 核心原因&#xff1a;USB Serial 设备&#xff0c;没有被识别为 COM 口你现在看到的 USB Serial&#xff0c;说明开发板已经正常启动了&#xff0c;USB 也被电脑识别到了&#x…...

多模型聚合平台如何助力网站AIB测试与选型

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 多模型聚合平台如何助力网站AIB测试与选型 对于网站产品经理而言&#xff0c;首页文案的生成质量直接影响用户的第一印象和转化率。…...

如何快速实现U盘文件自动备份:USBCopyer终极指南

如何快速实现U盘文件自动备份&#xff1a;USBCopyer终极指南 【免费下载链接】USBCopyer &#x1f609; 用于在插上U盘后自动按需复制该U盘的文件。”备份&偷U盘文件的神器”&#xff08;写作USBCopyer&#xff0c;读作USBCopier&#xff09; 项目地址: https://gitcode.…...

Linux 负载均衡的 cache_nice_tries:缓存友好的迁移尝试

简介现如今服务器、嵌入式设备、工控主板普遍采用多核、NUMA 架构 CPU&#xff0c;多进程多线程并发运行模式成为常态。Linux 内核依靠调度域分层负载均衡机制&#xff0c;分散 CPU 运行压力&#xff0c;避免单核心负载过高、其余核心空闲浪费硬件算力。但任务跨核心迁移是一把…...

Visual C++运行库一键安装指南:彻底解决Windows应用依赖问题

Visual C运行库一键安装指南&#xff1a;彻底解决Windows应用依赖问题 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist 你是否曾经遇到过打开软件时弹出"缺少…...

终极Windows风扇控制指南:FanControl让你的电脑安静又高效

终极Windows风扇控制指南&#xff1a;FanControl让你的电脑安静又高效 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Trendin…...

终极虚拟显示器解决方案:ParsecVDisplay完整使用指南

终极虚拟显示器解决方案&#xff1a;ParsecVDisplay完整使用指南 【免费下载链接】parsec-vdd ✨ Perfect virtual display for game streaming 项目地址: https://gitcode.com/gh_mirrors/pa/parsec-vdd ParsecVDisplay是一个基于Parsec虚拟显示驱动(VDD)的独立应用程序…...