【数据结构初阶】第七篇——二叉树的顺序结构及实现(堆的向下,向上调整算法)

简介: 【数据结构初阶】第七篇——二叉树的顺序结构及实现(堆的向下,向上调整算法)

二叉树的顺序结构


普通二叉树是不适合用数组来存储的,因为可能会导致大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

image.png

堆的概念及结构


堆的概念

堆:如果有一个关键码的集合K={k0,k1,k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足ki<=k2i+1且ki<=k2i+2(或满足ki>=k2i+1且ki>=k2i+2),其中i=0,1,2...,则称该集合为堆。

小堆:将根节点最小的堆叫做小堆,也叫作最小堆或小根堆。

大堆:将根节点最大的堆叫做大堆,也叫最大堆或大跟堆。

堆的性质:

堆中某个节点的值总是不大于或不小于其父节点的值。

堆总是一颗完全二叉树。

堆的结构

image.png

堆的向下调整算法


现在我们给出一个数组,逻辑上可以看作是一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

image.png

但是,使用向下调整算法需要满足一个前提:


   若将其调整成小堆,那么根节点的左右子树必须都为小堆。


   若将其调整成大堆,那么根结点的左右子树必须都为大堆。


向下调整算法的基本思想(这里以小堆为例):


1.从根节点处开始,选出左右孩子中值较小的孩子。


2.让小的孩子与其父亲进行比较。


若小的孩子比父亲还小,则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整,知道调整到叶子节点为止。


若小的孩子比父亲大,则不需处理了,调整完成,整个树已经是小堆了。

//交换函数
void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
//堆的向下调整(小堆)
void AdjustDown(int* a, int n, int parent)
{
  //child记录左右孩子中值较小的孩子的下标
  int child = 2 * parent + 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 = 2 * parent + 1;
    }
    else//已成堆
    {
      break;
    }
  }
}

 使用堆的向下调整算法,最坏的情况下就是一直交换,需要循环的次数为:h-1(h为树的高度),而 h = log2(N+1)(N为树的总结点数).所以堆的向下调整算法的时间复杂度为:O(logN) 。

  上面说到,使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行,那么如何才能将一个任意树调整为堆呢?

 答案很简单,我们只需要从倒数第一个非叶子结点开始,从后往前,按下标,依次作为根去向下调整即可。

代码:

  //建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(php->a, php->size, i);
  }

堆的向上调整算法


当我们在一个堆的末尾插入一个数据后,需要对堆进行调整,使其仍然是一个堆,这时需要用到堆的向上调整算法。

image.png

向上调整算法的基本思想(以建小堆为例):

1.将目标结点与其父结点比较。

2.若目标结点的值比其父节点的值小,则交换目标节点与其父节点的位置,并将原目标节点的父节点当作新的目标节点继续进行向上调整。若目标节点的值比其父节点的值大,则停止向上调整,此时该树已经是小堆了.

代码如下:

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
  HPDataType tmp = *x;
  *x = *y;
  *y = tmp;
}
//堆的向上调整(小堆)
void AdjustUp(HPDataType* 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;
    }
  }
}

堆的实现


初始化堆


  首先,必须创建一个堆类型,该类型中需包含堆的基本信息:存储数据的数组,堆中元素的个数以及当前堆的最大容量。

typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
  HPDataType* a;//用于存储数据的数组
  int size;//记录堆中已有元素个数
  int capacity;//记录堆的容量
}HP;

堆的初始化和顺序表很相似基本上什么都不用做,只要指针置空,大小和容量置为0即可。

void HeapInit(HP* hp)
{
  assert(hp);
  hp->a=NULL;
  hp->capacity=hp->size=0;

销毁堆


为了避免内存泄漏,使用完动态开辟的内存空间后都要及时释放该空间,所以,一个用于释放内存空间的函数是必不可少的。

//销毁堆
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);//释放动态开辟的数组
  php->a = NULL;//及时置空
  php->size = 0;//元素个数置0
  php->capacity = 0;//容量置0
}

打印堆


void HeapPrint(HP* php)
{
  for (int i = 0; i < php->size; ++i)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}

堆的插入


数据插入时是插入到数组的末尾,即树形结构的最后一层的最后一个结点,所以插入数据后我们需要运用堆的向上调整算法对堆进行调整,使其在插入数据后仍然保持堆的结构。

//堆的插入
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  if (php->size == php->capacity)
  {
    HPDataType* tmp = (HPDataType*)realloc(php->a, 2 * php->capacity*sizeof(HPDataType));
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    php->a = tmp;
    php->capacity *= 2;
  }
  php->a[php->size] = x;
  php->size++;
  //向上调整
  AdjustUp(php->a, php->size - 1);
}

堆的删除


堆的删除,删除的是堆顶的元素,但是这个删除过程可并不是直接删除堆顶的数据,而是先将堆顶的数据与最后一个结点的位置交换,然后再删除最后一个节点,再对堆进行一次向下调整。


原因:我们若是直接删除堆顶的数据,那么原堆后面数据的父子关系就全部打乱了,需要全体重新建堆,时间复杂度为O ( N ) O(N)O(N)。若是用上述方法,那么只需要对堆进行一次向下调整即可,因为此时根结点的左右子树都是小堆,我们只需要在根结点处进行一次向下调整即可,时间复杂度为O ( log ⁡ ( N ) ) O(\log(N))O(log(N))

//堆的删除
void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置
  php->size--;//删除最后一个结点(也就是删除原来堆顶的元素)
  AdjustDown(php->a, php->size, 0);//向下调整
}

获取堆顶的数据


获取堆顶的数据,即返回数组下标为0的数据

//获取堆顶的数据
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];//返回堆顶数据
}

获取堆的数据个数


获取堆的数据个数,即返回堆结构体中的size变量

//获取堆中数据个数
int HeapSize(HP* php)
{
  assert(php);
  return php->size;//返回堆中数据个数
}

堆的判空


堆的判空,即判断堆结构体中的size变量是否为0

//堆的判空
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;//判断堆中数据是否为0
}

建堆的时间复杂度


image.png

相关文章
|
15天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
76 29
|
15天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
15天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
2天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
147 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
1天前
|
算法
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。