[数据结构]二叉树(下)

一、二叉树的节点和深度关系

1.满二叉树

我们可以假设二叉树有N个节点,深度为h我们可以恒容易得到满二叉树每行的节点数,然后错位相减,算出节点与高度的关系。

2.完全二叉树

注意我这个是因为最后一行的节点数为1。

二、向上调整建堆和向下调整建堆的时间复杂度差异

1.向上调整建堆

现在我们有一个数组,我们要让它向上调整建堆

我们知道时间复杂度考虑的是最坏情况,现在我们来思考每一层向上调整需要的次数:

第一次不需要,第二层最多一次,以此类推,我们能退出以下关系式:

也就是:

2.向下调整建堆        

我们可以想象一下:

深度为h时,第一层每个节点的最大调整次数时h-1

深度为h时,第二层每个节点的最大调整次数时h--2

深度为h时,第三层每个节点的最大调整次数时h--3

深度为h时,第四层每个节点的最大调整次数时h--4

以此类推,倒数第二层每个节点的最大调整次数为1

最后一层每个节点的最大调整次数为0

因此我们可以得到这样一个关于它的时间复杂度

F(h)=2^(h-1)+2^(h-2)*2+.....+2^3*(h-3)+2^2*(h-2)+2^1*(h-1)

我们可以通过错位相减法,可以得到。

F(h)=2^(h-1)+2^(h-2)+2^(h-3)+....+2^2+2^1-(h-1)

F(N)=N-log(N+1)

通过与向上调整建堆,我们不难得到,这种情况下.向下调整建堆的效果更好.

三、堆的使用与堆排序

现在我们我思考如果我有这样的一个数组:

{0,3,1,4,6,9,2,7,5,8},如果我们要用堆让它完成一个升序的排列,我们应该选择建大堆还是建小堆呢?不少人可能会选择建小堆,但是如果我们完成了小堆,我们会发现:

我们只取出了最小值,很明显,这种方法是不行的。

所以这里我们选择建大堆。

void AdjustDown(HPDataType* a, int n, int parent)
{
	int 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;
		}
	}
}
void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}
void HeapSort(int* a, int n)
{
	for (int i = (n-1-1)/2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

而这种操作我们也称之为堆排序。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Node.js】CSR、SSR、SEO

SSR 和 CSR SSR &#xff08;Server-Side Rendering&#xff09;服务端渲染&#xff0c;请求数据和拼装都在服务端完成&#xff0c;相当于在服务端直接完成html。 而 Vue,react 等框架&#xff0c;是在客户端完成渲染拼接的&#xff0c;属于CSR&#xff08;Client-Side Rende…

Linux/openEuler系统部署spring boot+vue前后端分离项目(nginx均衡代理)

Linux/openEuler系统部署spring bootvue前后端分离项目&#xff08;nginx均衡代理&#xff09; 1、系统环境准备&#xff0c;安装openjdk和nginx还有MySQL&#xff0c;咱们本文先连接主机mysql进行登录&#xff08;linux上的mysql服务可以先不安装&#xff09; 可以看我前面的…

【神经网络】得分函数,损失函数~

目录 引言 一、神经网络概述 1 定义 2 基本原理 二、得分函数 1 定义 2 应用方法 3 与神经网络 三、损失函数 1 定义 2实现方法 3 与神经网络 四、得分函数与损失函数的协同作用 1 关系 2 实际应用 六、代码事例 &#xfffc;、总结与展望 引言 在人工智能与机…

40 openlayers setCenter 之后 绘制了Overlay 地图定位异常

前言 这是之前在 生产环境碰到的一个问题 这个其实就是 业务上一个地图点击点位展示详情, 然后再点击另外一个点位 展示详情, 切换中心店的这个过程 其主要的问题是 使用 openlayers 的 Map.View.setCenter() 了之后, 整个地图的中心点切换到了一个莫名其妙的地方 然后 经…

Linux的学习之路:2、基础指令(1)

一、ls指令 上篇文章已经说了一点点的ls指令&#xff0c;不过那还是不够的&#xff0c;这篇文章会介绍更多的指令&#xff0c;最起码能使用命令行进行一些简单的操作&#xff0c;下面开始介绍了 ls常用选项 -a 列出目录下的所有文件&#xff0c;包括以 . 开头的隐含文件。 -d…

3.4网安学习第三阶段第四周回顾(个人学习记录使用)

本周重点 ①CSRF跨站请求伪造 ②跨域访问 ③文件包含 ④文件上传 ⑤文件下载漏洞 ⑥XXE外部实体注入 本周主要内容 ①CSRF跨站请求伪造 一、概述&#xff1a; csrf: cross site request forgrey 跨站请求伪造。当攻击者不能通过常用的手段获取cookie时候&#xff0c;…

SQL Server 2008R2 日志文件大小设置及查询

SQL Server 2008R2 建立数据库存在日志无限增长问题&#xff0c;造成磁盘内存不足。本文解决这个问题&#xff0c;如下&#xff1a; 1.设置日志文件的最大大小 USE master; GO ALTER DATABASE [D_total] MODIFY FILE (NAME D_total_log, -- 日志文件的逻辑名称MAXSIZE 200…

信号处理--基于FBCSP滤波方法的运动想象分类

目录 理论 工具 方法 代码获取 理论 通用空间模式 (CSP) 算法可以用来有效构建最佳空间滤波器区分&#xff0c;然后实现运动想象的数据中的脑电信号的区分。然而&#xff0c;空间滤波器性能的好坏主要取决于其工作频带。如果脑电信号没有经过滤波或者滤波的频带范围不合适…

计算机组成原理 微程序控制器组成实验

一、实验目的 1.掌握时序产生器的组成原理。 2.掌握微程序控制器的组成原理。 3.掌握微指令格式的化简和归并。 二、实验任务 1、按实验要求连接实验台的数码开关K0-K5、按钮开关、时钟信号源和微程序控制器。注意&#xff1a;本次试验只做微程序控制器本身的实验&#xf…

安科瑞ANET智能物联网网关 通信管理机-安科瑞 蒋静

概述 本系列智能通信管理机是一款采用嵌入式硬件计算机平台&#xff0c;具有多个下行通信接口及一个或者多个上行网络接口&#xff0c;用于将一个目标区域内所有的智能监控/ 保护装置的通信数据整理汇总后&#xff0c;实时上传主站系统&#xff0c;完成遥信、遥测等能源数据采集…

基于Java+Spring Boot+MySQL的二手手机管理系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是墨韵&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c;不进则退。学习如赶路&#xff0c;不能慢一步。 目录 一、项目简介 二、开发技术与环…

【项目自我反思之vue的组件通信】

为什么子组件不能通过props实时接收父组件修改后动态变化的值 一、现象二、可能的原因1.响应式系统的限制2.异步更新队列3.父组件和子组件的生命周期4.子组件内部对 props 的处理 三、组件通信的几种场景&#xff08;解决方案&#xff09;1.子组件想修改父组件的数据2.子组件传…

Rust GUI学习 小部件系列(一):如何在iced窗口中使用颜色选择器colorpicker

注&#xff1a;此文适合于对rust有一些了解的朋友 iced是一个跨平台的GUI库&#xff0c;用于为rust语言程序构建UI界面。 前言&#xff1a; 本系列是iced的小部件应用介绍系列&#xff0c;主要介绍iced、iced_aw两个库中涉及的各种小部件的使用及实例演示。 本文所介绍的是co…

Redis入门到入坑(一)

Redis入门到入坑&#xff08;一&#xff09; Redis缓存入门简介Redis初始操作Redis数据存储操作 Redis常用数据类型简介String类型操作实践Hash类型应用实践List类型应用实践Set类型应用实践 Java中操作redis准备工作Jedis的应用快速入门实现RedisTemplate应用项目工程实践 Red…

嵌入式安全性基础知识-计算机系统安全知识+信息安全基础+网络安全协议-嵌入式系统设计师备考笔记

0、前言 本专栏为个人备考软考嵌入式系统设计师的复习笔记&#xff0c;未经本人许可&#xff0c;请勿转载&#xff0c;如发现本笔记内容的错误还望各位不吝赐教&#xff08;笔记内容可能有误怕产生错误引导&#xff09;。 本章的主要内容见下图&#xff1a; 1、计算机系统系统…

设计模式——2_6 观察者(Observer)

这世界没有一件事情是虚空而生的&#xff0c;站在光里&#xff0c;背后就会有阴影&#xff0c;这深夜里一片寂静&#xff0c;是因为你还没有听见声音 ——马良《坦白书》 文章目录 定义图纸一个例子&#xff1a;在RPG游戏里应对善变的天气定义元素Area & Weather 给 Area 和…

Linux--Ubuntu安装【保姆级教程】

Linux操作系统时程序员必须要学的操作系统。接下来我们就来看一下Linux操作系统是如何安装的 我们在 Vmware 虚拟机中安装 linux 系统&#xff0c;所以需要先安装 vmware 软件&#xff0c;然后再 安装 Linux 系统。 一.所需安装文件&#xff1a; Vmware 下载地址(现在最新版的…

蓝桥刷题--N皇后和最近公共祖先

1.N皇后 #include<iostream> using namespace std;const int N 12; int vis[N][N], n, ans;void dfs(int dep) {// 在这个搜索中dep表示行&#xff0c;i表示列// 1 搜索出口if(dep n 1){ans;return;}// 2 继续搜索for(int i 1; i < n; i){// 2.1 排除非法情况if(v…

SQL-Labs靶场“34-35”关通关教程

君衍. 一、34关 POST单引号宽字节注入1、源码分析2、联合查询注入3、updatexml报错注入4、floor报错注入 二、35关 GET数字型报错注入1、源码分析2、联合查询注入3、updatexml报错注入4、floor报错注入 SQL-Labs靶场通关教程&#xff1a; SQL注入第一课 SQL注入思路基础 SQL无列…

TWT:一个让WiFi6更省电的特性

更多精彩内容在公众号。 再wifi6前&#xff0c;已经有了不少节能特性&#xff1a;PSM,PSMP,APSD。在一个 Beacon 周期内&#xff0c;终端 会观察 AP 是否会向其发送数据&#xff0c;如果是&#xff0c;那么终端就保持等待&#xff0c;直到接收完成后&#xff0c; 才会进入休眠模…