初阶数据结构之---二叉树的顺序结构-堆

引言

今天要讲的堆，不是操作系统虚拟进程地址空间中（malloc，realloc等开空间的位置）的那个堆，而是数据结构中的堆，它们虽然名字相同，却是截然不同的两个概念。堆的底层其实是完全二叉树，如果你问我，完全二叉树是什么。好吧，那我先从树开始讲起，开始我们今天的内容。

树是什么？

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

  • 有一个特殊的结点，称为根结点，根节点没有前驱结点
  • 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。

上图的三个结构都不是树，不符合子树之间无交集的定义，子树相交其实就成了图。

关于树的常见概念

  1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
  2. 叶节点/终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
  3. 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
  4. 双亲节点/父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
  5. 孩子节点/子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点树的高度/深度：树中节点的最大层次； 如上图：树的高度为4
  6. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
  7. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。

以上是学习堆要了解的基本概念。

对于树结构的模拟

虽然树已经有了很多限制和规则，但其还是有着很大的灵活性，我们根据其结构特性也给出了一些定义方案。

1.如果明确了树的度，那么可以定义TreeNode

typedef struct TreeNode
{
	int data;
	struct TreeNode* child1;
	struct TreeNode* child2;
	struct TreeNode* child3;
	//。。。
}TreeNode;

像上述代码中定义的那样，可以固定定义一种固定度数的结点。

2.左孩子右兄弟表示法

struct Node
{
    int data;//结点中的数据
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
};

实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

但我们用的正真多的，是二叉树

二叉树是什么？

二叉树的概念

二叉树是特殊的树

一棵二叉树是结点的一个有限集合，该集合:

  1. 或者为空
  2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

上图中我们可以看出：

1. 二叉树的度不大于2（每个结点最多有两个孩子）

2. 二叉树有左右之分，次序不能颠倒因此二叉树是有序树

当然，以下几种情况也符合二叉树的定义，都是二叉树

二叉树的存储结构

二叉树一般可以使用两种存储结构，一种是顺序结构，一种链式结构。

1.顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，而这就引入到了我们今天要讲的堆。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储

二叉树的链式存储结构是指，用链来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

特殊的二叉树

1. 满二叉树：一个二叉树的每一层都是满的，如果一个树的层数为K，且结点数为2^k - 1，则它就是满二叉树。

2.完全二叉树：如一个树的深度为h，前h-1层都是满的，最后一层不满但连续。

下图中，左边的是满二叉树，右边的是完全二叉树

  • 完全二叉树是一种效率很高的数据结构，堆的逻辑结构实则就是一个完全二叉树。

二叉树顺序结构实现（堆）

普通的二叉树（我们可以称为非完全二叉树）是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

如果强行用堆表示普通的二叉树，就会像下面这样：

如果用完全二叉树实现，那么就是这样：

现在应该能体会到两种实现的区别了吧

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

堆的性质：

  • 一颗完全二叉树
  • 大堆：树中任何一个父亲都大于等于孩子
  • 小堆：树中任何一个父亲都小于等于孩子

在这个堆中，如果你细心观察，可以发现如下规律（这个规律很重要）：

知道父亲下标（parent）找孩子（child）：

  • 左孩子下标（leftchild）=  parent * 2 + 1
  • 右孩子下标（rightchild）=  parent * 2 + 2

知道孩子下标（child）找父亲（parent）：

  • parent  =（child - 1）/  2

用代码模拟堆的结构，就是以下这样

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;//存放堆数据的数组
	int _size;//堆数据个数
	int _capacity;//堆的容量-可扩容
}Heap;

下面我们默认先建一个小堆，后期如果需要改大堆只需要变动相应比较符号就可以

堆的插入

如果存在一个有十个元素的堆，想要往其中插入一个新的元素，其过程是下面这样

以下是插入部分的代码实现

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
    //如果空间不够就扩容
	if (hp->_size == hp->_capacity) {
		int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL) {
			perror("realloc fail:");
			exit(1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
    //向上调整算法
    AdjustUp(hp->_a, hp->_size - 1);
}

在这里，将新插入的10这个元素往上调整的过程，我们称之为向上调整，涉及到一个算法，那就是向上调整算法，现在我们来实现一份。

向上调整算法

在比较交换元素的过程中，我们提供一个比较函数以便交换元素

//交换
void my_swap(HPDataType* a, HPDataType* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

 以下就是对向上调整的实现

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
    //如果孩子为0则比较结束
	while (child > 0) {
		if (a[parent] > a[child]) {
			my_swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else break;
	}
}
  1. 找相比较的父子结点：根据堆中父子结点位置规则，先找到需要比较检查调整的父子结点
  2. 比较父子结点大小：如果建立小堆，且子节点小于父节点，交换父子结点数据；如果此时子节点大于父节点，跳出循环
  3. 更新父子结点：将父节点的位置赋给child，同时更新parent
  4. 检查是否退出循环：如果child==0时，跳出循环

堆的创建

下面我们给出一个数组的元素，建成一个堆。在刚刚讲完堆的插入和向上调整过后，其实创建堆就显得格外容易了。我们只需要从数组中取出元素，然后依次插入到堆中便可以完成堆的创建，以下是实现代码：

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
    //初始化堆时，别忘记初始化以下hp中的元素
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
	for (int i = 0; i < n; i++) {
		HeapPush(hp, a[i]);
		AdjustUp(hp->_a, hp->_size - 1);
	}
}

堆的删除

堆的删除，通常意义上是删除堆顶的元素。如果建的是小堆，那么堆顶的元素就是堆中最小的数；如果建的是大堆，那么堆顶就是堆中最大的元素。

想要删除堆顶元素，不能通过整体向前移动后面的堆元素的方式来删除元素，因为这样会打乱元素之间的父子关系，打乱了父子关系，整个堆就很有可能不符合“父亲一定小于等于（或大于等于）孩子”这一规则了。

真正的实现方式是，将堆顶元素和堆底元素互换位置，将size - 1，再将此时堆顶的元素进行向下调整。

过程见下图：

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size != 0);
	my_swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
    //向下调整
	AdjustDown(hp->_a, hp->_size, 0);
}

既然讲到了向下调整，其实就又涉及到了向下调整算法。

向下调整算法

向下调整，顾名思义就是将元素往下调，先给大家展示调整代码，再来解析过程

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n) {
		if (child + 1 < n && a[child + 1] < a[child]) {
			child++;
		}
		if (a[parent] > a[child]) {
			my_swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
  1. 找相比较的父子结点：根据堆中父子结点位置规则，先找到需要比较检查调整的父子结点，这里先预设左孩子比右孩子小，当发现右孩子更小时，child + 1，在比较左右孩子之前，还需要考虑到child + 1不会导致越界
  2. 比较父子结点：父节点大于子结点时（此时建立的是小堆），交换父子结点数据；如果父节点小于字结点，跳出循环
  3. 更新父子结点：将child赋给parent，计算新的child，进入新一轮循环
  4. 判断循环结束：当孩子跃出数据存储范围时，循环结束

取堆顶的数据

这里没什么好说，堆的数组中第一个元素就是堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size != 0);
	return hp->_a[0];
}

堆数据的个数和堆的判空

这里直接用堆中的size元素就OK

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

堆的销毁

跟顺序表的销毁基本一致

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = 0;
	hp->_size = 0;
}

到这里堆的实现基本上就结束了

体验一下手写的堆

#include"heap.h"
int main()
{
	Heap hp;
	int arr[] = { 5,4,3,2,1 };
	HeapCreate(&hp, arr, sizeof(arr) / sizeof(int));
	printf("%d\n\n", HeapSize(&hp));
	while (!HeapEmpty(&hp)) {
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	return 0;
}

结语

今天的内容到这里就结束了，本篇博客带大家认识了一下树和堆，但这里只是带大家稍微看了看堆的实现。关于堆的内容其实还有很多，topk问题，堆排序，优先级队列中会更深入的带领大家去了解和使用堆，在下一篇数据结构中，会更深入的挖掘一些堆的应用，并计算一下其时间复杂度，让大家体会到堆的魅力。如果还想了解更多有趣的内容，还请多多支持博主，比心♥

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

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

相关文章

electron 程序与安装包图标放大与制作

electron 程序与安装包图标放大与制作

原因 electron-builder 在打包时需要最小支持到256x256像素的icon图标。原有历史图标都太小了。需要尝试将图标放大。 工具 convertio.co/zh/ico-png/ 在线ico转png网站 https://github.com/upscayl/upscayl 图片放大工具 csdn下载 greenfish-icon-editor-pro.en.softonic.c…
阅读更多...
Tomcat 的安装(详细教程)

Tomcat 的安装(详细教程)

目录 一、概述二、安装前准备三、Windows 安装1. 方式一2. 方式二 一、概述 官网&#xff1a;https://tomcat.apache.org/ Tomcat 是一个免费的、开放源代码的 Web 应用服务器&#xff0c;属于轻量级应用服务器&#xff0c;由 Apache、Sun 和一些公司以及个人共同开发而成&…
阅读更多...
【MapReduce】03.MapReduce框架原理

【MapReduce】03.MapReduce框架原理

目录 1.InputFormat数据输入 1.1.切片与MapTask并行度决定机制 1.2.Job提交流程源码和切片源码 1.3.FileInputFormat切片机制 1.4.TextInputFormat 1.5.CombineTextInputFormat切片机制 1.6.CombineTextInputFormat 1.InputFormat数据输入 1.1.切片与MapTask并行度决定…
阅读更多...
Qt开发QHostInfo主机地址查询组件

Qt开发QHostInfo主机地址查询组件

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QHostInfo组件实现对主机地址查询功能…
阅读更多...
IP地址：现代网络通信的基础

IP地址：现代网络通信的基础

IP地址&#xff08;Internet Protocol Address&#xff09;是指互联网协议地址&#xff0c;又译为网际协议地址。它是IP协议提供的一种统一的地址格式&#xff0c;为互联网上的每一个网络和每一台主机分配一个逻辑地址&#xff0c;以此来屏蔽物理地址的差异。这种地址形式使得互…
阅读更多...
第九篇 – 过程发现（Process Discovery）是如何赋能数字化市场营销全过程？- 我为什么要翻译介绍美国人工智能科技巨头IAB公司

第九篇 – 过程发现（Process Discovery）是如何赋能数字化市场营销全过程？- 我为什么要翻译介绍美国人工智能科技巨头IAB公司

IAB平台&#xff0c;使命和功能 IAB成立于1996年&#xff0c;总部位于纽约市。 作为美国的人工智能科技巨头社会媒体和营销专业平台公司&#xff0c;互动广告局&#xff08;IAB- the Interactive Advertising Bureau&#xff09;自1996年成立以来&#xff0c;先后为700多家媒体…
阅读更多...
【Python】成功解决AttributeError: ‘MyClass‘ object has no attribute ‘my_attribute‘

【Python】成功解决AttributeError: ‘MyClass‘ object has no attribute ‘my_attribute‘

【Python】成功解决AttributeError: ‘MyClass’ object has no attribute ‘my_attribute’ &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门…
阅读更多...
魅力女神节•巾帼绽芳华 | 联诚发开展三八国际妇女节慰问活动

魅力女神节•巾帼绽芳华 | 联诚发开展三八国际妇女节慰问活动

为进一步丰富女职工精神文化生活&#xff0c;展现新时代巾帼风采&#xff0c;弘扬积极向上、奋勇争先的精神风貌。3月8日&#xff0c;联诚发LCF开展了三八妇女节慰问活动&#xff0c;为全体女职工送上温馨的祝福和节日的问候。 清晨&#xff0c;活动现场便已经装饰一新&#xf…
阅读更多...
【kerberos】hadoop集群使用keytab认证的逻辑

【kerberos】hadoop集群使用keytab认证的逻辑

一、背景&#xff1a; haoop的kerberos认证核心是org.apache.hadoop.security.UserGroupInformation类。 UserGroupInformation一般有两种&#xff1a;&#xff08;1&#xff09;apache原生的&#xff08;2&#xff09;cdh hdp改良过的&#xff0c;即cloudera改良过的。 由此衍…
阅读更多...
基于SpringBoot校园失物招领系统的设计与实现(程序+数据库+文档)

基于SpringBoot校园失物招领系统的设计与实现(程序+数据库+文档)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…
阅读更多...
Linux操作系统的vim常用命令和vim 键盘图

Linux操作系统的vim常用命令和vim 键盘图

在vi编辑器的命令模式下&#xff0c;命令的组成格式是&#xff1a;nnc。其中&#xff0c;字符c是命令&#xff0c;nn是整数值&#xff0c;它表示该命令将重复执行nn次&#xff0c;如果不给出重复次数的nn值&#xff0c;则命令将只执行一次。例如&#xff0c;在命令模式下按j键表…
阅读更多...
RabbitMQ篇

RabbitMQ篇

1.初始MQ 1.1. 同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;…
阅读更多...
计算机网络——23网络层导论

计算机网络——23网络层导论

网络层导论 网络层服务 在发送主机和接收主机对之间传送段&#xff08;segment&#xff09;在发送端将段封装到数据报中在接收端&#xff0c;将段上交给传输层实体网络层协议存在于每一个主机和路由器路由器检查每一个经过它的IP数据报的头部 网络层的关键功能 网络层功能 …
阅读更多...
探秘WiFi 6技术：特性与优势解析

探秘WiFi 6技术：特性与优势解析

随着科技的飞速发展&#xff0c;无线网络技术也在不断演进&#xff0c;WiFi 6&#xff08;802.11ax&#xff09;作为最新一代的无线网络标准&#xff0c;正逐渐成为新一轮技术革新的引领者。本文将深入探讨WiFi 6模块的特性和优势&#xff0c;揭示其在无线通信领域的巨大潜力。…
阅读更多...
（3）应用与信息

（3）应用与信息

文章目录 前言 3.1 FlightDeck FrSky发射器应用程序 3.2 MAVLink2数据包签名(安全) 3.3 MAVLink高延迟协议 3.4 无线地面站连接中继器 1 概述 2 组件 3 设置 3.5 遥测无线电区域条例 3.6 用于OpenTX的Yaapu遥测脚本 前言 FlightDeck FrSky Transmitter AppMAVLink2 …
阅读更多...
sizeof和strlen的详细万字解读

sizeof和strlen的详细万字解读

sizeof和strlen的对比 sizeof不是函数 侧面证明sizeof不是函数 如果是函数 应该需要有括号 不能落下来 strlen 只针对字符串 包含头文件 string.h 并且这个是个函数 随机数值 sizeof里面有表达式的话 表达式里面是不参与计算的 下面的s求出的是4 就是因为是不参与计算的 不…
阅读更多...
重学SpringBoot3-WebMvcConfigurer接口

重学SpringBoot3-WebMvcConfigurer接口

重学SpringBoot3-WebMvcConfigurer接口 WebMvcConfigurer基本信息为什么WebMvcConfigurer能配置底层行为实现WebMvcConfigurer举例1. 自定义格式化器和转换器2. 添加拦截器3. 配置静态资源4. 配置视图控制器 上一篇文章对 SpringMVC 重要配置类—— WebMvcAutoConfiguration 类…
阅读更多...
httprunner结合pytest的自动化框架结构

httprunner结合pytest的自动化框架结构

2. 项目结构 2.1. 初代项目结构 3. 用例结构 - pytest 3.1. 单接口用例结构 # NOTE: Generated By HttpRunner v4.3.5 # FROM: testcases\data\data_20240229_test.json from httprunner import HttpRunner, Config, Step, RunRequestclass TestCaseData20240229Test(HttpRu…
阅读更多...
数据集生成 YOLOV5 可训练的数据目录、并且可视化

数据集生成 YOLOV5 可训练的数据目录、并且可视化

1、前言 YOLOV5 训练数据的目录结构如下&#xff1a; 如果有测试集的话&#xff0c;也按照下面目录摆放即可 注意&#xff1a;这里的图片和标签文件名要严格对应&#xff01;&#xff01;后缀除外 关于YOLOv5介绍或者yolo格式的介绍参考之前专栏&#xff0c; 2、划分数据生成…
阅读更多...
WPF 消息提示 类似toast方式

WPF 消息提示 类似toast方式

WPF里面的消息提示一般都是MessageBox.Show()&#xff0c;这种样式不是很好看&#xff0c;所以就想办法重新搞了一个类似弹出消息的功能。原理很简单&#xff0c;就是弹出一个新窗体&#xff0c;然后等几秒窗体自动关闭。 先上效果图&#xff1a; 新建一个MsgHelper.cs类&…
阅读更多...
最新文章

Copyright @ 2022~2023