数据结构——树，二叉树和堆（万字详解）

发布于：2023-01-04 ⋅ 阅读:(436) ⋅ 点赞:(0)

文章目录

⭐树与堆

✨树

image-20220702162549595

🎃树是一种非线性的数据结构，由n个结点组成的一个具有层次关系的集合，根结点在第一层，向下延伸展开。

🎈一个特殊的结点称为根结点，如上图结点A，该结点没有前驱结点。

🎈除根结点外，其余结点会分成n个互不相交的子树，每棵子树的根结点有且只有一个前驱，可以有0个或多个后继结点。

🎈树是递归定义的。

注意：

  1. 树的子树不能相交（相交成环叫图，而不叫树）。
  2. 每个结点有且仅有一个双亲结点，根结点无前驱结点。
  3. 一棵N个结点的树有N-1条边。

🌠树的基本术语

image-20220702163356663

🥝结点的度

一个结点子树的个数就是该结点的度，如A的度是2，B的度是2，F的度是0。

🥝树的度

具有子树数量最多的结点，其度称为树的度，如A的度为2；若一棵树的最大度为2，该数也称为二叉树。

🥝叶子结点/终端结点

度为0的结点，如D, H, F I和J结点都为叶子结点。

🥝分支结点/非终端结点

与叶子结点相反，度不为0的结点。

🥝双亲结点/父结点

若一个结点有子结点，则该结点称为双亲结点，如A为B和C的双亲结点，B为D和E的双亲结点等。

🥝子结点

有双亲结点的结点为子结点。

🥝兄弟结点

具有与其他结点相同的双亲结点，如D与E的双亲结点都为B，则它们互为兄弟结点。

🥝结点层次

从一棵树的根开始计数，根结点所在层数为第一层（如A），根的子结点为第二层（B,C），一直到最后一层的结点(H, I J)为最后一层，即第三层。

🥝树的深度/高度

树中结点的最大层次，空结点的树高度为0，如该图有4个层次，则树的深度为4。

🥝堂兄弟结点

两个不属于同一双亲结点，但它们的双亲结点又处于同一层的结点互称为堂兄弟结点，如E和F，H和I互为堂兄弟结点。

🥝结点祖先

从根结点到任一子结点所经过分支上的所有结点，如A是所有结点的祖先。

🥝子孙结点

以某结点为根的子树任一结点都成为该结点的子孙，如所有结点都是A的子孙结点。

🥝森林

有n棵互不相交的树的集合为森林（n > 0）。

🌠树的结构定义

由以上种种树的结点间关系可知，一棵树的结点结构体内部信息不仅要需要存储数值信息，还要明确各结点之间的双亲和兄弟关系。树的结构定义可以有多重方式：如双亲表示法，孩子表示法，孩子双亲表示法等，而相对较优的一种方式为——孩子兄弟表示法（只需两个指针即可），具体定义如下代码所示：

typedef int TEtype;
typedef struct Tree
{
    TEtype data;					//存储数据信息
    struct Tree* FirstChild;		//指向该结点下第一个孩子结点的结构体指针
    struct Tree* NextBrother;		//指向该结点同一结点层级的下一个兄弟结点
}Tree;

以该代码定义结构为基础，对上例树进行代码原理图分析：

image-20220702172053153

🎈树的应用：文件系统

image-20220702172253822

由此可知，在用树表示的目录结构中，从根目录到任何数据文件，仅有唯一一条路径可以到达，因为树的结构是不相交的。

✨二叉树

一颗树中，每个结点最多拥有两个子结点（度为2）的树称为二叉树。

image-20220702172921625

  1. 一个根结点的左侧称为左子树（A左侧的B，D构成的左子树），右边称为右子树（C,E,G,F构成的右子树），次序不能颠倒，二叉树是有序树。

  2. 一颗树只要满足结点的度最大为2即为二叉树，一棵树可能满足二叉树的要求，但一颗二叉树必定满足树的所有定义；树的基本概念都可以用到二叉树上，如兄弟，双亲或祖先结点等。

  3. 二叉树有二叉链和三叉链两种表示方式，二叉链一般指孩子表示法，三叉链指孩子双亲表示法，这两种方式是二叉树最常见的表示方式，其他的还有孩子兄弟表示法，但本质也是二叉链。

🌠二叉树的分类

🥝满二叉树

image-20220702173745220

  1. 除了叶结点，度都是满（度为2）的结点的树，称为满二叉树。

  2. 满二叉树的结点个数遵循指数规律，深度为k，由根结点所在的第1层开始，每层的结点数都是2k-1次方，如A所在第一层结点个数为20 = 1，第二层结点个数为21 = 2，第三层为22 = 4个结点，第k层为2(k-1)个结点。

🥝完全二叉树

image-20220702173706239

  1. 一棵树有k层，前k-1层都是满的，但最后一层不满，但最后一层从左到右的结点是连续的树称为完全二叉树。

  2. 因为二叉树区分左右子树，如果最后一层仅有右结点而没有左结点，则不能称为完全二叉树，如下图：

image-20220702175201954

🎃前两棵树不是完全二叉树，因为完全二叉树除了前K-1层都必须全都为度为2的结点外，最后一层K的结点必须对于每个双亲结点从左到右依次占满才为完全二叉树，可以不将该层2K-1个结点都占满，但数据必须连续存储，如果占满即为满二叉树。

  1. 在一颗完全二叉树中，某一个结点没有其左孩子，则该结点一定是叶子结点。
  2. 有N个结点的完全二叉树深度为log2N + 1。

🌠二叉树的性质

  1. 规定根结点的层数为1，则一棵非空二叉树的第k层上最多有2(k-1)个结点，若为满二叉树，则该棵树最多共有2k-1个结点。

  2. 对于任意二叉树，若度为0的叶结点个数为N0，度为2的分支结点个数为N2，则可以根据n2的个数计算出N0的个数，计算公式如下：N0 = N2 +1。

  3. 具有N个结点的满二叉树的深度k为log2(N + 1)。

  4. 深度为k的完全二叉树，这一类树中最少和最大结点取值范围：2(k-1)< k < 2k - 1，最少为最后第k层只有一个结点的情况，而最多为k层的满二叉树情况。

📜题目练习

  1. 某二叉树共有 399个结点，其中有 199个度为2的结点，则该二叉树中的叶子结点数为( )

    A 不存在这样的二叉树

    B 200 (用到性质2)

    C 198

    D 199

  2. 在具有2n个结点的完全二叉树中，叶子结点个数为( )
    A n

    B n + 1

    C n - 1

    D n/2

⭕说明：深度为n的完全二叉树，前n-1层是满二叉树，最后一层从左到右连续但不满。根据性质3，一个完全二叉树中，度为0结点n0的总是比度为2的结点n2多一个，而度为1的结点n1在完全二叉树中最多仅有1个（或没有），则有公式n0 + (n0 - 1) + n1 = 2n，化简为2*n0 - 1 + n1 = 2n，又因为n1要么为0，要么为1；如果为0则因为偶数减1得到奇数，再除以2得到小数，而结点不能是小数，所以n1只能为1，刚好与-1约掉，得到n0 = n，则本题选A。

  1. 一棵完全二叉树的结点数为531个，那么这棵树的高度为（ )

    A 11

    B 10

    C 8

    D 12

⭕说明：高度为h的完全二叉树，其结点取值范围由最多和最少所界定，如果是最多，则该完全二叉树变成了满二叉树，则根据性质2，最大结点数为2h - 1；而最少时即最后一层只有1个叶结点，根据等比数列，第h层（最后一层）的前一层h - 1层的结点数排满，再在最后一层加1个结点，有2(h-1) - 1 + 1，括号中的h-1为倒数第二层，-1为等比公式所带，+1为最后一层仅有一个结点的意思，两者抵消得完全二叉树的n层最小结点公式：2(h-1)，所以深度h的取值范围总结为2(h-1)< h < 2h - 1，带入计算上下限可得只有10满足，选B。

  1. 一个具有767个结点的完全二叉树，其叶子结点个数为（）

    A 383

    B 384

    C 385

    D 386

⭕说明：原理同题2，根据性质3，判断n0，n1与n2的关系，n2 = n0 - 1，n1要么为1，要么为0，其中n0数量的总和就是需要计算的叶结点个数。有2* n0 - 1 + n1 = 767，要保证n0为整数，则n1必须为0，使2* n0 = 768计算可得n0 = 384，选B。

  1. 一颗拥有1000个结点的树度为4，则它的最小深度是（ ）

​ A 5

​ B 6

​ C 7

​ D 8

⭕说明：如果这棵树每一层都是满的，则它的深度最小，假设它为一个四叉树，高度为h，则这个数的节点个数为(4^h - 1) / 3，当h = 5, 最大节点数为341， 当h = 6, 最大节点数为1365，所以最小深度应该为6。

  1. 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个

    A 11

    B 12

    C 13

    D 14

⭕说明：两个公式：N个结点有N - 1条边

​ 边与度的关系：N - 1 = N1 + 2 * N2

总结点个数为N，由度为0，为1和为2的结点组成，所以N = N0 + N1 + N2。带入公式有N0 + N1 + N2 - 1 = N1 + 2 * N2，两边约去得到N0 - 1 = N2，所以得到度为2的结点个数为3 - 1 = 2，同时又已知N1个数为8，所以总结点个数为3 + 8 + 2 = 13。

🌠二叉树的存储结构

二叉树分为普通二叉树，满二叉树和完全二叉树。普通二叉树因为数据可能存在不连续性（每层的结点不占满），如果使用顺序表进行存储，则数据可能会存在跳跃的情况而不符合顺序表连续存储数据的性质：

image-20220702184125314

🥝则普通二叉树的存储结构采用链表的方式定义，因为链表在内存中不连续存储，所以能对数据的存储进行特定指向而不至于浪费空间。

链式二叉树的数据结构代码定义如下：

typedef int BTEtype;
typedef struct BinaryTree
{
    BTEtype data;					//链式二叉树的数值存储				
    struct BinaryTree* left;		//双亲结点的左子结点结构体指针
    struct BinaryTree* right;		//双亲结点的右子结点结构体指针
}BT;

具体链式二叉树的函数定义与功能将会在后续章节详细阐述。

🥝对于完全二叉树或满二叉树，因为该类树的数据连续性，则可选择顺序表的存储结构模式对这两类树进行数据存储和访问。其存储原理图如下所示：

image-20220702184917560

使用顺序表进行完全/满二叉树的数据存储和访问主要有以下两大优点：

  1. 可以很容易计算双亲与子结点间的下标位置关系：

    🍕left = (parent * 2) + 1

    🍕right = (parent * 2) + 2

    以上图满二叉树为例，根结点A下标为0，其左子结点B的下标为0 x 2 + 1 = 1，右子结点的下标为0 x 2 + 2 = 2。再以B为双亲结点，表示D下标为1 x 2 + 1 = 3，E下标为1 x 2 + 2 = 4，具有非常明确的父子间的下标逻辑关系。

  2. 知道左右子结点下标也可以算出双亲结点位置：

​ 🍕parent = (child - 1) / 2

🎃C语言中，偶数 - 1再除以2，与偶数 - 2再除以2有相同结果，因为小数会被舍去，所以用统一的公式即可算出左结点或右子结点对应的双亲位置。

✨堆

堆是一种数据结构，它的存在主要是为了更快地筛选数据和进行海量数据的排序。在数据的存储和删除效率上并没有如同顺序表或链表那般方便和快捷，所以使用堆的情况之后仅对两方面进行介绍（堆的排序与TopK问题，主要针对海量数据的前K个筛选）。堆的逻辑存储结构是非线性的一棵完全二叉树，而本质在物理空间上是在内存中基于顺序表的存储方式。

✨堆的分类

堆的逻辑结构是一颗完全二叉树，在这类树中存在两类排序方式完全不同的堆，称为小根堆和大根堆。

🥝小根堆：树中所有的双亲结点值都小于或等于其子结点的值。

image-20220702193035960

数组中的数据不是从小到大排列的，而是只要双亲结点下标对应位置的值不大于其子结点下标对应位置值即可。

🥝大根堆：树中所有的双亲结点都大于或等于其子结点的值。

image-20220702192143701

物理结构上看，数组中并不是按降序排列数值，表面看上去数组并没有特别明显的规律存储可言。而在逻辑上看，只要双亲结点下标对应位置的值不小于其子结点下标对应值即可。

⭕大小堆构建意义：

  1. 小根堆和大根堆存在的意义是用于堆排序，时间复杂度最少为O(N * logN)，比冒泡排序算法或直接插入排序算法时间复杂度的O(N2)更快。
  2. topk问题：能在海量数据中找出最大或最小的部分数据，耗时短速度快。

✨堆的性质

堆总是一棵完全二叉树，虽然逻辑上是一棵树的形状，但在物理内存的存储使用的是一块连续的线性存储空间。

🎃以小堆举例，原理图如下：

image-20220702193804912

堆中某个结点的值总是不小于（大根堆）或不大于（小根堆）其双亲结点的值。

✨堆的实现

一个堆的建立和数据的插入删除并不是像逻辑与物理都为线性结构的顺序表的那样简单，虽然其本质上是以顺序表的结构基础进行数据存取和访问的，但仍需要了解其逻辑上存储结构的不同并以此进行堆的顺序表下标对应位置数值的操作。

堆遵循完全二叉树的数据插入逻辑，当数据仅有在上一层结点占满，并于当前层的二叉树中某个连续数据的后边才可进行数据的继续尾插。插入堆的数据只会影响根结点连接到该插入数据位置之间一条路径上的所有双亲与祖先结点。

🎃以大堆插入数据为例，插入原理图如下：

堆插入

🥝小堆存储中，尾插的新数据先与其双亲结点值比较，若该子结点值比双亲结点值更小，则与其双亲结点进行值得交换。交换后再将该已交换的双亲结点值与祖先双亲结点进行比较，如果子比双亲小则交换，否则不交换，则该数插入与数值顺序调整完成。

🥝大堆存储同上图所示，同样需要将插入值与双亲比较， 如果比双亲更大则交换数值，否则不交换。

🌠堆的结构定义

堆的结构使用顺序表定义，其好处是可以对存储于堆中的任意数据进行随机访问，且方便寻找子，兄弟或双亲结点。其定义方式与顺序表大体相同，但仍存在略微差异。

🎀堆结构

typedef int HPEtype;
typedef int(*COM)(int, int);	//建大堆/小堆的函数指针的宏
typedef struct heap
{
	HPEtype* arr;				//指向堆数据内存空间指针
	int size;					//堆顺序表有效数据个数
	int capacity;				//堆顺序表空间最大容量
}HP;
  1. 堆的结构定义因为是基于顺序表而创建的，所以其基本结构整体与顺序表类似。除了该结构外，还需要宏定义一个函数指针，用于规定堆排序的规则，方便数据插入时控制建堆规则，即小根堆或大根堆的选择。
  2. 这个函数指针的类型使用typedef重命名为COM，用于在之后传递比较数据的规则，如大堆插入时比较父子节点值，或向下调整时比较兄弟结点值孰大孰小等。

🎀函数指针COM类型指向的比较函数

bool Bigger(HPEtype a, HPEtype b)		//大堆规则
{
	return a > b;
}

bool Smaller(HPEtype a, HPEtype b)		//小堆规则
{
	return a < b;
}

若if判断语句调用Bigger规则，当比较两者值时传入该函数，前者比后者大时条件判断为真，否则为假而不进入向下调整的if子函数，主要控制向下或向上调整算法，一般用于大根堆的数值插入或大堆的建立，小根堆同理。

🌠堆初始化

给堆的结构体成员变量初始化方式与顺序表大体相同。

🎀堆初始化函数

HP* HPInit()
{
	HP* NewArray = (HP*)malloc(sizeof(HP));			//开辟堆的结构体信息空间，并将空间地址返回于临时结构体指针指向
	assert(NewArray);
	NewArray->arr = NULL;							//初始化堆中成员数组指针置空
	NewArray->capacity = NewArray->size = 0;		//初始化堆的初始容量和有效数据个数为0
	return NewArray;								//将结构体指针指向地址返回给实参
}

该函数用于堆结构的初始化定义，其中包含了堆信息结构体空间的开辟，堆中数组空间，容量和有效数值的置空。堆的排序规则rule不在该初始化函数中定义好，而是在堆插入，删除函数中传递堆排序规则。

🌠堆插入

堆的数值插入逻辑和其他线性数据结构的差异性就体现出来了，因为堆的数据虽然存储在顺序表里，每次数据的插入更新在物理逻辑上都是顺序表的连续尾插，但其逻辑结构却是一棵完全二叉树，数据依次排列在最后一层连续结点的后方，且需要根据小堆或大堆间，子与双亲结点间的关系而调整数据的位置，这里就涉及到了数据位置的调整，具体可如下原理图观察数据插入与位置的调整过程（小堆规则为例）：

堆插入

  1. 堆的每次数据插入，除了根结点仅有的一个数据外，其余数据在子结点中都需要与其双亲结点进行值的比较。大堆的规则为双亲结点的值总是不小于子结点值，所以当子结点值比双亲结点值大时，就需要进行子父结点间的数值交换。小堆同理，规定双亲结点值总是不大于其子结点对应值，如果子结点值小于其双亲结点值时，就需要交换。
  2. 因为子结点与双亲结点间的值需要进行两两比较，并且该过程是由插入的结点值向上与其双亲结点值之间的比较，所以需要单独额外定义向上比较和位置调整函数AdjustUpward，用于比较子父结点值同时，交换值；且因为两者交换后，以原双亲结点为子结点，再向上与其他祖先结点比较时也可能不满足大小堆的规则要求，仍需要进行循环比对和交换数据，所以一个向上调整函数内应该对该插入结点一直到根结点整一条路径的完整对比和交换循环才可以完全满足堆的规则。
  3. 向上调整的最好情况是插入的数据立即满足堆的要求而不需要进行数值交换，也就不需要再向上对比双亲与祖先的值及交换了。而最坏情况出现在，大堆插入的值比所有该条路径上的双亲或祖先结点的值都大，或小堆都小时，对比和交换的过程步骤一直要持续到根结点交换后才算结束，所以该函数的平均时间复杂度为O(N * logN)。

🎀堆插入函数

void HPPush(HP* root, HPEtype x, COM rule)			//传参堆根结点地址，待插入值和比较规则
{
	assert(root);
	if (root->capacity == root->size)						//顺序表插入扩容
	{
		int expand = root->capacity == 0 ? 4 : root->capacity * 2;
		HPEtype* NewSpace = (HPEtype*)realloc(root->arr, sizeof(HPEtype) * expand);
		assert(NewSpace);
		root->arr = NewSpace;
		root->capacity = expand;
	}
	root->arr[root->size] = x;								//数据尾插到顺序表
    root->size++;											//尾插后有效数据个数+1
	AdjustUpward(root->arr, root->size - 1, rule);			//尾插数据的向上调整
}

🎀向上调整算法代码参考：

void AdjustUpward(HPEtype* arr, int child, COM rule)//传参为待调整数组，子结点下标和比较规则
{
	assert(arr);
	int parent = (child - 1) / 2;				//堆尾子结点对应的双亲结点下标
	while (child)								//当子结点不为堆顶元素时
	{
		if (rule(arr[child], arr[parent]))		//传入父子比较规则，当子比父大或小时进入函数
		{
			Swap(&arr[child], &arr[parent]);	//交换子父结点值
			child = parent;						//父结点下标赋值给子下标
			parent = (child - 1) / 2;			//新的父结点下标根据新的子下标计算而得
		}
		else
		{
			break;		//如果父子数值间关系满足大小堆要求，则不进行数值交换和向上遍历，退出函数
		}
	}
}
  1. 插入的数据作为子结点，与其对应的双亲结点数值间进行比较，当满足堆间父子间关系时直接跳出函数，无需交换和调整位置。只有父子结点间数据不符合堆规律，以及交换后的父与祖先间的数值关系都不满足堆排序要求时才继续循环，最坏情况的循环结束条件是以根结点作为子结点时，向上没有更多数据需要比较，则向上调整全部结束，该路径上的所有父子与祖先结点都进行了数值交换。以下原理图为大堆数据插入最好（插入5，都比祖先结点值小）与最坏（插入15，都比祖先结点值大）的两种情况：

堆插入1

🎀数值间交换函数代码

void Swap(HPEtype* a, HPEtype* b)
{
	*a ^= *b;
	*b ^= *a;
	*a ^= *b;
}

🎃因为本章均以整数作为数之间的比较和交换，且如果两数相同就不进入交换步骤，所以采用异或方法进行数值交换，但其他类型的数据则可能无法适用（所以最好的方式还是采用中间变量的交换模式）。

🌈测试用例1——小堆构建和数据插入

HP* root = HPInit();
int array[11] = { 2,7,26,25,19,17,1,90,3,36 };		//乱序数组建小堆
int* pa = array;
while (*pa)
{
    HPPush(root, *pa, Smaller);		//小堆规则Smaller逐个插入数据建小堆
    pa++;
}
int i = 0;
int size = sizeof(array) / sizeof(array[0]) - 1;
while (size)
{
    printf("%d ", root->arr[i]);		//遍历观察
    i++;
    size--;
}

🌈观察结果的物理结构

1 3 2 7 19 26 17 90 25 36

🌈逻辑结构

image-20220703162015619

可见以小堆规则构建和插入的堆数据，其逻辑结构在插入完成和向上调整后均符合双亲结点值不大于子结点值的规则。

🌈测试用例2——大堆构建和数据插入

HP* root = HPInit();
int array2[13] = { 14,66,25,4,76,88,18,97,77,82, 3, 2 };
int* pa = array2;
while (*pa)
{
    HPPush(root, *pa, Bigger);		//大堆规则Bigger逐个插入数据建大堆
    pa++;
}
int i = 0;
int size = sizeof(array2) / sizeof(array2[0]) - 1;
while (size)
{
    printf("%d ", root->arr[i]);
    i++;
    size--;
}

🌈观察结果的物理结构

97 88 76 77 82 25 18 4 66 14 3 2

🌈逻辑结构

image-20220703162530539

数据间满足大堆排序父子间结点关系（每个双亲结点总是不小于子结点数值），所以堆插入和向上调整过程正确。

🎃堆插入总结：

  1. 一个数组可以通过将其中的值逐个取出并按照堆的插入规则（使用向上调整算法）放入新开辟的堆空间里，使其成为堆（如上述定义插入方式），也可以通过堆的规则对数组自身进行改造，使其中的数值遵循堆的排列规则（两种建堆方式），并且此方式不需要预先构建堆的结构，后者会在后面的堆排序中详细说明，而前者主要用于插入数据到堆结构中。
  2. 将一个数据插入到上述已初始化的堆空间中，因为是顺序表定义，所以难免内存空间的扩容开辟，其作用等同于顺序表中的扩容检查CheckCapacity。本例中，按照以往的方式，当堆空间仅初始化未开辟时，则一次扩容4个于插入数值类型对应的字节空间，若堆空间满则将空间扩大一倍。
  3. 与顺序表一样，经过简单的扩容检查和数据插入（即尾插）后，如果我们要开辟的堆是小根堆，即所有的双亲节点（父节点）都小于或等于其子节点，或大根堆，即所有的双亲节点大于或等于其子节点，则都可以通过一种称为“向上调整”的算法来排序数值而成为满足特定堆的结构，该向上调整算法的时间复杂度为O(N*logN)。
  4. 插入的子节点child总是堆的末节点元素，而其父节点parent元素的下标刚好是子下标减1再除以2，并且无论子左节点或子右节点都满足这样的关系式。
  5. 在if判断条件中引用了函数指针传递的数值比较规则rule，是用户在外部传入的函数数值比对规则，Bigger函数为大堆排序的父子间数值比大，Smaller为小堆排序中父子间数值比小，再结合上调与下调函数，可以很轻易交换父子数据并完成迭代循环。

⭕小提示：观察指针指向的内存地址后的内存和值，可以在监视窗口，指针后加逗号和观察的值的个数，如arr, 10可以观察指向数组arr的指针的其后值。

🌠堆删除

堆的数据删除一般指对于堆顶元素的去除，将顶上元素去除后，余下的数据仍需要保持堆的结构。回忆堆的结构优势，其最大的特点能让我们直接从堆顶元素访问和取出整个结构中的最大或最小值，如果删除其最顶值，余下的元素在物理存储结构上看组成了新的数组，但在逻辑结构上已经不再具有大小堆结构，此时父子兄弟间的关系全部乱套，以刚才测试用例的大堆为例：

97 88 76 77 82 25 18 4 66 14 3 2

如果直接去除堆顶元素的最大值，余下元素为：

88 76 77 82 25 18 4 66 14 3 2

数据堆的逻辑结构为：

image-20220703200748295

看似其仍满足大堆结构，但对比原图，数值88与76原本是兄弟结点，此时变为了父子关系，还有82与25，原本是堂兄弟结点关系，此时变为了亲兄弟结点，堆内部数据的结点间关系完全乱套，所以直接删除堆顶元素的方法是完全错误的。

仍然想让其堆顶保持最值且余下数据保持完全二叉树的堆结构的话，可以采取两种策略：

🥝将堆顶数据删除，余下元素全部重新进行堆插入操作

该种操作时间成本太高，因为在遍历原顺序表的过程中同时需要对数据进行向下调整，则整体时间复杂度为O(N2)，不推荐该种方法。

🥝堆首尾数据交换——向下调整法

另一种比较高效的方法是将堆顶和堆尾的数据进行首尾交换，将该元素剔除（伪删除，直接将size–，使顺序表访问不到）后，将原堆尾而现被交换至堆顶的数据进行向下调整。向下调整的原理大体与向上调整相同，即为了保持原本堆的性质与结构，将新的堆头结点值与其子孙结点进行逐一比较，若在大堆中发现其子结点值大于该根结点，或小堆中子结点值小于该根结点值，则需要进行父子结点值交换，只要遇到子结点比双亲结点更大或更小，则循环要一直持续下去，直到子结点下标大于或等于整个数组范围size即停止交换（最坏情况）。

原理图如下：

堆删除

🎀堆顶删除函数

void HPPop(HP* root, COM rule)
{
	assert(root);
	if (!HPEmpty(root))			//如果堆不为空，才执行堆顶删除
	{
		Swap(&root->arr[0], &root->arr[root->size - 1]);//先将堆首尾元素交换
		root->size--;									//size--以剔除原堆顶元素
        AdjustDownward(root->arr,root->size, 0, rule);	//将交换到堆顶的原堆尾元素向下调整
	}
}

其中，对于堆删除中使用到的堆判空函数

🎀堆判空函数

bool HPEmpty(HP* root)
{
	assert(root);
	return root->size == 0;
}

当存储堆数据的顺序表size为0时，代表该堆中没有任何数据，无法进行删除，反之可以。

🎀向下调整算法

void AdjustDownward(HPEtype* arr, int size, int parent, COM rule)
{					//传参为待调整数组，数组大小，父节点下标和对比规则
	assert(arr);
	int child = parent * 2 + 1;
	while (child < size)		//调整结束条件为不超出新的size范围
	{
		if (child + 1 < size && rule(arr[child + 1], arr[child]))	//左右子下标比较
		{
			child = child + 1;
		}
		if (rule(arr[child], arr[parent]))		//父子值比较
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = child * 2 + 1;				//调整后，继续向下迭代对比
		}
		else
		{
			break;
		}
	}
}
  1. 采用首尾交换并删除堆尾数据对比前一种算法的最大好处是，可以仅改变堆头数据，而使整个堆的左子树和右子树的堆结构维持不变，即仍然遵循父子间结点关系和大小堆规则，仅需要对堆头数据向下调整与其他子孙结点间的关系，调整数值位置即可。
  2. 向下调整算法中，需要传入的参数为顺序表指针arr，数组大小size，可规定的需要向下调整的根结点parent，以及大小堆排序规则rule。观察函数，其中定义了需要与传入的根结点对比数值大小的子结点下标，当该下标不超出整个数组size的范围或根结点对比子结点已经满足了堆的排序规则时，就跳出调整循环。
  3. 以上图小堆为例，当需要向下调整的根结点比其左子结点和右子结点都大时，此时需要进入调整循环的第一个if判断，因为根结点默认与左子结点的值相比较，如果右子结点的值比左子结点的值还要小，则根结点需要与更小的右子结点进行换位，并将该交换过数值的子结点下标更新赋值给根结点，再以该根结点下标*2+1去寻找该结点对应左子结点的下标，继续向下对比和换位循环即可。
  4. 为了方便观察堆插入和堆删除的规律变化，可以定义堆取顶函数，以对进行堆插入或删除后的堆顶元素进行监视。

🎀堆取顶函数

HPEtype HPTop(HP* root)
{
	assert(root);
	if (HPEmpty(root))		//如果堆为空，则返回无意义值-1
	{
		return -1;
	}
	return root->arr[0];	//堆取顶，将数组首元素值返回
}

🌈测试用例——大堆取顶：

//堆初始化
HP* root = HPInit();
//堆插入和堆删除&取堆顶
HPPush(root, 5, Bigger);
HPPop(root, Bigger);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 4, Bigger);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 6, Bigger);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 5, Bigger);
printf("堆顶元素为：%d\n", HPTop(root));
HPPop(root, Bigger);
HPPush(root, 3, Bigger);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 7, Bigger);
printf("堆顶元素为：%d\n", HPTop(root));

🌈观察结果

image-20220704140125701
  1. 步骤1进行了堆数据插入后再删除，此时为空堆，空堆取顶返回无意义值-1。
  2. 步骤3和4分别数据插入，因为是大堆结构，所以堆顶总是数值最大的数，所以后续在步骤5中将堆顶最大值元素删除后，再将3压入堆中，此时堆顶的最大元素为5，所以取顶输出5。
  3. 步骤6压入比原堆顶更大的数据7，所以此时的大堆堆顶元素变为7，取顶输出。

🌈测试用例——小堆取顶

HP* root = HPInit();
HPPush(root, 5, Smaller);
HPPop(root, Smaller);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 4, Smaller);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 6, Smaller);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 5, Smaller);
printf("堆顶元素为：%d\n", HPTop(root));
HPPop(root, Smaller);
HPPush(root, 3, Smaller);
printf("堆顶元素为：%d\n", HPTop(root));
HPPush(root, 7, Smaller);
printf("堆顶元素为：%d\n", HPTop(root));

🌈观察结果

image-20220704140645829

🎃先堆插入5再删除，堆为空返回-1。再依次插入4,6,5三个元素，因为是小堆存储，所以取最小数据存于堆顶，因此插入多个数据堆顶均为4。将堆顶删除后，再依次堆插入3和7，此时3成为整个堆中最小的元素，所以后续取堆顶值均为3。

🌠堆遍历

对堆进行遍历一般指对堆顶取数据再将其删除，将整一个堆不断依次取顶并删除直至堆中数据为空的操作即遍历完全整个顺序表。但因为堆结构的特殊性，不断取堆顶并输出打印的过程中，如果是大堆取顶，则打印出的数据是降序的，因为每次取顶都是当前堆中数据的最大值，将最大值取顶并删除后，下一次取顶变为剩余数据的次大值，取完数据后即遍历完全整个顺序表，并自动将数据从大到小排列了出来。小堆原理相同，因为每次取到的数据都是整个堆中的最小值，所以遍历完全后数据自动为升序打印。

以大堆遍历为例，原理图如下：

堆遍历打印

🌈遍历堆函数

void HPPrint(HP* root, COM rule)
{
	assert(root);
	if (HPEmpty(root))					//如果堆为空，则无法遍历
	{
		printf("堆为空，无法遍历\n");
		return;
	}
	while (!HPEmpty(root))				//非空堆，则依次循环取顶再去堆顶，直至堆整个为空便停止循环打印
	{
		printf("%d ", HPTop(root));
		HPPop(root, rule);
	}
}
  1. 堆的遍历好处是方便观察堆中存在的所有数据，并且以堆结构的天然优势就可以将数据自动排序成升序或降序，因为堆顶的数据永远都是最大或最小值。
  2. 堆的遍历前提为堆结构的存在，以及堆中含有数据，其弊端在于如果一个代码库中没有预先定义好的堆结构与其相关的上下调整函数，堆删除或插入函数等，就不能为一个数组进行堆的遍历和输出排序；另一个弊端在于，遍历打印出的数据看似虽然已经排好序，但本质上并不是对数组本身数据进行升降序排序，而只是客观清空了堆中顺序表的所有元素，在控制台中打印出来了排好序中的便于观察的有序数组而已。
  3. 所以如果需要对一个数组本身进行排序，堆的遍历排序并不是一个好的方法，具体的堆排序规则和建堆方式将在后续章节中有所介绍。

🌈测试用例

HP* root = HPInit();
HPPrint(root, Bigger);
HPPush(root, 2, Bigger);
HPPush(root, 6, Bigger);
HPPush(root, 77, Bigger);
HPPush(root, 9, Bigger);
HPPush(root, 0, Bigger);
HPPop(root, Bigger);
HPPrint(root, Bigger);

🌈观察结果

堆为空，无法遍历
9 6 2 0

🎃第一次对空堆打印，因为堆中无任何数据，此时size为0，所以无法打印。后续进行部分数据的堆插入和删除，因为是以大堆规则进行的，且遍历原理为取顶再删顶，所以最终打印出来的数据以降序打印。

🌠堆销毁

基于顺序表创建的堆，释放时将指向堆结构的顺序表空间释放，再将存储堆信息的结构体空间释放即可。

🎀堆销毁函数

HP* HPDestroy(HP* root)
{
	assert(root);
	free(root->arr);		//先释放顺序表
	free(root);				//再释放堆结构体信息空间
	root = NULL;			//将堆指针置空并返回
	return root;
}

🌈测试用例

image-20220704164429408

📜题目练习

  1. 下列关于向下调整算法的说法正确的是（ ）

    A 构建堆的时候要对每个结点都执行一次

    B 删除操作时要执行一次

    C 插入操作时要执行一次

⭕说明：建堆只需从最后一个非叶子结点开始，一直到根结点，依次每个执行一次向下调整即可。删除时先首尾交换，再执行一次向下调整，而插入只需要执行向上调整算法即可。

  1. 在一个堆中，根节点从0开始编号，下标为 i（i > 0） 的结点的左右孩子结点及父结点的下标分别是（ ）

    A 2 i、2 i + 1、i /2

    B 2i、2i + 1、(i - 1)/2

    C 2i + 1、2i + 2、(i - 1)/2

    D 2i + 1、2i + 2、i/2-1

⭕说明：牢记公式🍕left = (parent * 2) + 1；🍕right = (parent * 2) + 2；🍕parent = (child - 1) / 2。

  1. 将一个顺序表利用向下调整的方式整理成堆的时间复杂度为O(N)

⭕说明：向上调整建堆为O(logN)，向下调整建堆为O(N)。

⭐后话

  1. 博客项目代码开源，获取地址请点击本链接：[CSDN-树和堆 · VelvetShiki_Not_VS。
  2. 若阅读中存在疑问或不同看法欢迎在博客下方或码云中留下评论。
  3. 欢迎访问我的Gitee码云，如果对您有所帮助还可以一键三连，获取更多学习资料请关注我，您的支持是我分享的动力~。
本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布