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

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

二叉树的顺序结构


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

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

相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
68 1
|
10天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
34 2
|
27天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
57 20
|
25天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
50 5
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
80 1
|
3天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
3天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
|
12天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
13天前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真

热门文章

最新文章