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

目录

满二叉树与完全二叉树高度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)


向上调整建堆:

介绍:

前提:上几层都是堆

先将数组内所有元素插入堆结构内,再从第一个元素到最后一个元素进行遍历,对每个元素使用向上调整算法,使堆结构成为大堆/小堆

复杂度推导:


向下调整建堆:

介绍:

前提:左右子树都是堆

先将数组内所有元素插入堆结构内,再从最后一个父亲的位置到第一个父亲的位置进行遍历,对每个元素使用向下调整算法,使堆结构成为大堆/小堆

复杂度推导:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/368427.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Web Based Quiz System v1.0 SQL 注入漏洞(CVE-2022-32991)

前言 CVE-2022-32991 是一个影响 Web Based Quiz System v1.0 的 SQL 注入漏洞。这个漏洞存在于 welcome.php 文件中的 eid 参数处。攻击者可以通过此漏洞在数据库中执行任意 SQL 语句&#xff0c;从而获取、修改或删除数据库中的数据。 具体细节如下&#xff1a; 攻击向量&…

无人机森林火灾解决方案

森林火灾解决方案 森林火灾特点 森林火灾发生突然、蔓延迅速、难以控制&#xff0c;应对难度系 数很高&#xff0c;扑救工作十分困难 救援面临的挑战 • 林区交通不便&#xff0c; 山高坡陡&#xff0c; 沟壑纵横&#xff0c;难以及时侦查、 定位、扑灭 • 火灾发生的区域…

基于opencv的斜光测距及python实现

1.前言 最近做了一个基于opencv的斜光测距的小项目&#xff0c;东西不多&#xff0c;但是很有意思&#xff0c;值得拿出来学一学。项目里面需要比较精确的定位功能&#xff0c;将前人matlab代码移植到python上&#xff0c;并且做了一些优化&#xff0c;简化逻辑(毕竟我是专业的…

马工程刑法期末复习笔记重点2

马工程刑法期末复习笔记重点2

【JavaWeb程序设计】环境配置和Web工程的创建

目录 一、安装JDK、Tomcat&#xff0c;进行测试Tomcat能否正常启动。 二、修改Tomcat端口为8976&#xff0c;重新进行测试 三、使用集成开发环境Intelligent Idea&#xff0c;绑定JDK和Tomcat&#xff0c;建立站点&#xff0c;并测试 四、编写一个简单的html页面&#xff0…

微信小程序遮罩层显示

效果展示&#xff1a; wxml页面&#xff1a; <view classmodal-mask wx:if{{showModal}}><view class"modal-container"><view classmodal-content></view><view classmodal-footer bindtap"closeImage">//这个/images/ind…

SpringMVC的架构有什么优势?——控制器(一)

文章目录 控制器(Controller)1. 控制器(Controller)&#xff1a;2. 请求映射(Request Mapping)&#xff1a;3. 参数绑定(Request Parameters Binding)&#xff1a;4. 视图解析器(View Resolver)&#xff1a;5. 数据绑定(Data Binding)&#xff1a;6. 表单验证(Form Validation)…

Workerman在线客服系统源码,附搭建教程

源码介绍&#xff1a; Workerman在线客服系统源码。 workerman是一个高性能的PHP socket 服务器框架&#xff0c;workerman基于PHP多进程以及libevent事件轮询库&#xff0c;PHP开发者只要实现一两个接口&#xff0c;便可以开发出自己的网络应用&#xff0c;例如Rpc服务、聊天…

leetCode.98. 验证二叉搜索树

leetCode.98. 验证二叉搜索树 题目描述 代码 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(n…

秋招Java后端开发冲刺——并发篇2(JMM与锁机制)

本文对Java的内存管理模型、volatile关键字和锁机制进行详细阐述&#xff0c;包括synchronized关键字、Lock接口及其实现类ReentrantLock、AQS等的实现原理和常见方法。 一、JMM&#xff08;Java内存模型&#xff09; 1. 介绍 JMM定义了共享内存中多线程程序读写操作的行为规…

51单片机第18步_将TIM0用作13位定时器

本章重点学习将TIM0用作13位定时器。 1、定时器0工作在模式0框图 2、定时器0工作在模式0举例 1、Keil C51中有一些关键字&#xff0c;需要牢记&#xff1a; interrupt 0&#xff1a;指定当前函数为外部中断0&#xff1b; interrupt 1&#xff1a;指定当前函数为定时器0中断…

【C语言】union 关键字

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

ubuntu20.04配置调试工具

1.准备工作&#xff1a;安装g或者gdb sudo apt updatesudo apt install gg --versionsudo apt install gdbgdb --version 2.配置环境 2.1在本地新建一个main.cpp #include <iostream> #include <vector> #include <string>using namespace std;int main(…

克隆gitee仓库,在vs2022创建文件夹开发项目操作步骤

git网站 git知识大全 git教程&#xff1a;廖雪峰的官方网站 git菜鸟教程 gitee之创建项目步骤 同步源仓库 2. 克隆命令 3. 右击git Bash Here>粘贴命令行 4. 选中项目文件夹》创建本人文件夹&#xff08;ZYY&#xff09; 5. 打开vs2022》新建项目》选择Framework》下…

C++精解【10】

文章目录 读写文件概述example csv读文件读取每个字段读取机器学习数据库iris constexpr函数GMP大整数codeblock环境配置数据类型函数类 EigenminCoeff 和maxCoeffArray类 读写文件 概述 fstream typedef basic_fstream<char, char_traits<char>> fstream;此类型…

VSCode常用的一些插件

Chinese (Simplified) 汉语&#xff08;简体&#xff09;拓展包。 Auto Close Tag 可以自动增加xml/html的闭合标签。 CodeSnap 截图神器。截图效果在下面。 Dracula Official vscode一个很好看的主题。 Git Graph git管理工具。 GitHub Repositories 有了它&#xff0c;不…

前端利用vue如何实现导入和导出功能.md

1. 前端利用vue如何实现导入和到处功能 1.1. 导入功能&#xff08;以导入Excel文件为例&#xff09; 1.1.1. 实现步骤: 1.1.1.1. 安装依赖: 首先&#xff0c;你需要安装处理Excel文件的库&#xff0c;如xlsx。1.1.1.2. 创建上传组件: 使用Element UI的<el-upload>组件或其…

Qt:5.QWidget属性介绍(Enabled属性-控件可用性设置、geometry属性-控件位置/大小设置)

目录 一、 QWidget属性的介绍&#xff1a; 二、Enabled属性-控件可用性设置&#xff1a; 2.1Enabled属性的介绍&#xff1a; 2.2获取控件当前可用状态的api——isEnabled()&#xff1a; 2.3设置控件当前的可用状态的api—— setEnabled() &#xff1a; 2.4 实例&#xff…

git提交实战

以新项目为例&#xff0c;如何在新项目新分支提交代码。 1.查看文件所在位置 git init 2.克隆项目到本地并完成身份配置 3.将需要新增的文件放到指定目录路径下 4.进入新克隆的文件 cd XXX 5.切换分支 git checkout XXX 6.标红者即为新提交的文件 git status 7.加入 git …

Is ChatGPT a Good Personality Recognizer? A Preliminary Study?

ChatGPT是一个很好的人格识别者吗&#xff1f;初步调研 摘要1 介绍2 背景和相关工作3 实验3.1 数据集3.2 提示策略3.3 基线3.4 评估指标3.5 实现细节3.6 Overall Performance (RQ1)3.7 ChatGPT在人格识别上的公平性 (RQ2)3.8 ChatGPT对下游任务的人格识别能力&#xff08;RQ3&a…