数据结构-二叉树系统性学习（四万字精讲拿捏）

前言 

这里我会从二叉树的概念开始讲解，其次涉及到概念结构，以及堆的实现和堆排序。

目的是，堆比二叉树简单，同时堆本质上是二叉树的其中一种情况，堆属于二叉树顺序结构的实现

最后完善二叉树的讲解，也就是二叉树的链式结构的实现

二叉树的基本概念

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

有一个特殊的结点，称为根结点，根结点没有前驱结点

除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1）因此，树是递归定义的。

就像这样

这样

二叉树的基本性质

结点的度	一个结点含有的子树的个数称为该结点的度 如上图：A的为6（BCDEFG）
叶结点或终端结点	度为0的结点称为叶结点 如上图：B、C、H、I...等结点为叶结点（没有孩子的就是叶子节点）
非终端结点或分支结点	度不为0的结点 如上图：D、E、F、G...等结点为分支结点
双亲结点或父结点	若一个结点含有子结点，则这个结点称为其子结点的父结点 如上图：A是B的父结点
孩子结点或子结点	一个结点含有的子树的根结点称为该结点的子结点 如上图：B是A的孩子结点
兄弟结点	具有相同父结点的结点互称为兄弟结点 如上图：B、C是兄弟结点
树的度	一棵树中，最大的结点的度称为树的度 如上图：A树的度为6（最大的多少就是多少）（BCDEFG） 也就是有几个孩子 那么 H的度为0 E的度为2 以此类推
结点的层次	从根开始定义起，根为第1层，根的子结点为第2层 以此类推；（一般情况下从1开始 有些会从0开始） 但是为了方便计算，右兄弟左孩子的时候我是从0 开始的
树的高度或深度	树中结点的最大层次 如上图：树的高度为4 树的深度是4，因为从根节点A到最远的叶子节点F，需要经过4条边。
堂兄弟结点	双亲在同一层的结点互为堂兄弟 如上图：H、I互为兄弟结点
结点的祖先	从根到该结点所经分支上的所有结点 如上图：A是所有结点的祖先
子孙	以某结点为根的子树中任一结点都称为该结点的子孙 如上图：所有结点都是A的子孙
森林	由m（m>0）棵互不相交的树的集合称为森林 简单说 的说就是有好几个根节点，也就是好几个A组成（多棵树。并查集）

二叉树的定义

树的关键点是不知道定义几个树的度

1，明确知道的话我们可以写

2，不知道几个树的度，顺序表来写

3，右兄弟左孩子写法

不管多少，我们只定义两个树的度

特殊的二叉树：

1. 满二叉树：

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树：

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。从左到右必须连续（完全二叉树）

对比

右兄弟左孩子

右兄弟左孩子表示法，实际上是一种完全二叉树，需要按照顺序在二叉树里面进行放入

优缺点

优点

• 空间效率：这种写法允许我们使用数组来存储完全二叉树，而不需要为每个节点分配两个指针的空间。

• 简单性：它简化了对完全二叉树的遍历和操作。

缺点

• 限制性：这种方法只适用于完全二叉树，对于非完全二叉树，这种写法不适用。

• 复杂性：对于不熟悉这种表示法的人来说，理解和实现可能会有些复杂。

定义

 在定义里面不管多少，我们只定义两个树的度

逻辑讲解

右兄弟左孩子写法

在这种写法中，每个节点有两个子节点（左孩子和右兄弟），如果一个节点没有左子节点，那么它的左指针会指向它的右兄弟，而不是指向一个子节点。这种表示方法可以有效地利用数组来存储二叉树，同时保持树的结构信息。

例子

假设我们有以下完全二叉树：

在这个数组中，每个元素代表一个节点：

• A是根节点。
• B是A的左孩子。
• C是A的右兄弟。
• D是B的左孩子。
• E是B的右兄弟，同时也是C的左孩子。
• F是C的右兄弟。
• G是F的右兄弟。

简单的说就是，我们存储的时候，我们会按照顺序进行存储，A下面只放两个数值，放满了，我们就往A下面放，A下面放满了两个，我们往B下面放，循环套娃

树的存储方式

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。

存储方式

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

计算节点方式

我们可以通过计算找到父子节点，左右兄弟节点

节点计算总结

在数组中，我们可以通过节点的索引来确定其左孩子和右兄弟：

• 假设父亲在数组里面的下标为i

• 左孩子位于索引 2 * i + 1

• 右兄弟位于索引 2 * i + 2

• 假设孩子在数组里面的下标为j

• 父亲位于（j-1）/2

如果一个节点是叶子节点，或者在最后一层并且没有右兄弟，那么它的右兄弟指针将指向一个空值或者一个表示终止的特殊值。

二叉树使用注意事项

数组存储只适合满二叉树，或者特殊二叉树

像下面的情况就是不适合，不是不能实现，是不适合实现的

非完全二叉树，适合的实现方式方式是：二叉树链式结构实现

完全二叉树，适合的实现方式是：二叉树顺序结构的实现

下面我们实现，二叉树顺序结构的实现

二叉树顺序结构（堆）：堆的概念：

存储方式

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

还是那句话，堆是一种顺序结构实现的完全二叉树

在逻辑上不是连续的，但是在实际上，是数组进行实现的

堆的性质：

在数据结构中，“堆”是一种特殊的完全二叉树，它满足以下两个性质：

1. 结构性质：堆是一个完全二叉树，如果用数组表示，那么除了最后一层外，每一层都被完全填满，且最后一层从左到右填充。
2. 堆性质：树中任何节点的值都必须大于或等于其子节点的值（最大堆），或小于或等于其子节点的值（最小堆）。

最大堆（大堆）

在最大堆中，父节点的值总是大于或等于其子节点的值。这意味着堆中的最大值位于根节点。最大堆常用于实现优先级队列，其中最大元素具有最高的优先级。

特点：

• 根节点是堆中的最大元素。
• 任何父节点的值都不小于其子节点的值。

应用场景：

• 堆排序：在堆排序算法中，最大堆用于选择序列中的最大元素。
• 优先级队列：在需要频繁访问最大元素的场景中使用。

最小堆（小堆）

在最小堆中，父节点的值总是小于或等于其子节点的值。这意味着堆中的最小值位于根节点。最小堆同样用于实现优先级队列，但最小元素具有最高的优先级。

特点：

• 根节点是堆中最小元素。
• 任何父节点的值都不大于其子节点的值。

应用场景：

• 堆排序：在堆排序算法中，最小堆用于选择序列中的最小元素。
• 优先级队列：在需要频繁访问最小元素的场景中使用。

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

实现（小堆）

在实际的编程实现中，堆通常用数组来表示，因为这样可以有效地利用内存空间，并且可以快速地通过索引访问父节点和子节点。节点的索引和其父节点或子节点的索引之间有一定的关系：

• 父节点索引：(i - 1) / 2
• 左孩子节点索引：2 * i + 1
• 右孩子节点索引：2 * i + 2

其中 i 是节点的索引。

理解大堆和小堆的概念对于在实际应用中选择合适的数据结构和算法非常重要。

创建文件（小堆）

这里我们依旧是创建三个文件来实现顺序结构的堆

创建堆（小堆）

定义一个堆（Heap）的数据结构

这里所需要的头文件，是文件所需要的，这里不做过多解释，主要看的是定义的是数据结构，这里我们是用数组实现的

1. 定义数据类型 HPDataType：使用 typedef 创建了一个新的类型别名 HPDataType，这里指定为 int 类型。这意味着 HPDataType 可以用来声明整数类型的变量，但在堆结构中，它可以被用作更通用的数据类型。

2. 定义结构体 Heap：创建了一个结构体 Heap，它将用于表示整个堆的元数据和存储空间。

3. 成员变量：

   • HPDataType* _a：这是一个指针，指向堆中第一个元素的地址，用于访问和操作堆中的元素。
   • int _size：表示当前堆中元素的数量，即已使用的元素个数。
   • int _capacity：表示堆的最大容量，即 _a 指针所指向的数组能够容纳的元素个数。

这个结构体定义为后续实现堆的操作（如插入、删除、调整等）提供了必要的数据结构支持。在实际使用中，你还需要实现一些函数来操作这个 Heap 结构体，比如初始化堆、插入元素、删除最大元素（在最大堆中）或最小元素（在最小堆中）、销毁堆等。

创建了 Heap 结构体后，你通常会通过调用相关函数来初始化堆、使用它进行操作，并在最后销毁堆以释放分配的内存

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;//首元素地址
	int _size;//元素个数
	int _capacity;//元素容量
}Heap;

堆的初始化和销毁（小堆）

这里的初始化和销毁和顺序表的初始化以及销毁是差不多的

这里知识掌握不牢固的同学，可以看一下我写的顺序表的篇章

顺序表（增删减改）+通讯录项目（数据结构）+顺序表专用题型-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/137484207

//堆的初始化
void HeapInit(Heap* hp)
{
	//初始化这里不开辟空间
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	//这里不需要循环释放，因为这里是数组实现堆的
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

HeapInit 函数接收一个指向 Heap 结构体的指针 hp。这个函数的作用是将 hp 指向的 Heap 结构体初始化为一个空堆：

• _a 成员被设置为 NULL，表示没有分配任何内存空间。
• _capacity 成员被设置为 0，表示堆的最大容量目前为 0，即没有预留空间。
• _size 成员被设置为 0，表示堆中目前没有任何元素。

HeapDestory函数接收一个指向 Heap 结构体的指针 hp，并执行以下操作来销毁堆：

• 使用 assert 确保传入的 hp 不是 NULL。
• 使用 free 函数释放 _a 指针指向的内存空间。由于 _a 在 HeapInit 中被初始化为 NULL，这里释放前应确保 _a 非 NULL（这通常在其他函数中进行判断和分配）。
• 将 _a 设置回 NULL，确保指针不再指向任何内存空间。
• 将 _capacity 和 _size 重置为 0，恢复堆为一个空状态。

加入数据（小堆）

首先我们需要看堆实现的时候是如何调整的

1，这里最后一个数值是新加入的数值，那么此时我们需要向上调整，也就是我们需要和上一个父亲节点进行对比,

2，如果孩子节点小于父亲节点，那么我们就需要进行交换，因为小堆根是最小的数值

3，并且更新父亲节点想下标和孩子节点的下标

4，备注：这里我们不需要三方进行对比，意思就是，我们不需要三个数值进行对比，因为如果左孩子存在，按照这个逻辑，左孩子最后如果小于父亲节点就一定会进行交换，不小于就不会进行交换，然后插入右孩子时候，右孩子只需要和父亲进行比较就可以了，就算右孩子比父亲数值小，那么此时会和父亲节点进行交换，这个时候我们发现，左孩子一定大于或者等于右孩子，而右孩子也一定大于或者等于父亲节点，因为这里是小堆，越往上越小。

解释一下备注4：

此时我们发现，我们还没有插入左右孩子的节点

此时插入节点还没有交换

进行交换，此时我们发现左节点一定大于父亲节点

插入右孩子，此时还没有交换

进行交换，我们只需要对新插入数值和父亲节点进行对比就可以，不需要1,7,0 三个数值进行对比，从而决定交换不交换，因为左孩子一定小于父亲，如果父亲小于左孩子，交换之后，那么左孩子也一定小于右孩子

这里我们了解一下循环逻辑

循环三要素

1，初始条件

2，循环条件

3，结束条件

那么向上调整的结束逻辑应该是什么，那就是当插入的数值，也就是孩子元素下标到最上面的时候，也就是到0的时候，也就是应该结束循环，所以chile>0,这里是这一种情况也是三种情况下唯一不会产生越界的逻辑。

代码实现

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int chile)
{
	//获取父母所在位置
	int parent = (chile - 1) / 2;
	while (chile > 0)//这个循环条件不会越界，其余两个循环条件都会导致越界，但是也会正常运行
	{
		if (a[chile] < a[parent])
		{
			//传递地址，指针接收
			Swap(&a[chile], &a[parent]);
			//更新父母和孩子的下标
			chile = parent;
			parent = (chile - 1) / 2;
		}
		else
		{
			break;
		}
	}
 
	这个循环条件产生了越界，但是	printf("%d ", ps._a[-1]);（特别大） printf("%d ", ps._a[100]);（特别小）
	//while (a[chile] < a[parent])
	//{
	//	//传递地址，指针接收
	//	Swap(&a[chile], &a[parent]);
	//	//更新父母和孩子的下标
	//	chile = parent;
	//	parent = (chile - 1) / 2;
	//}
}
 
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断空间大小，并且开辟空间
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_a == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("HeapPush:tmp:");
			exit(1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	//插入
	hp->_a[hp->_size] = x;
	hp->_size++;
	//向上调整
	AdjustUp(hp->_a, hp->_size - 1);
}

AdjustUp 函数用于在插入新元素后，保持最小堆的性质。它接收一个数组 a 和一个元素的索引 child。这个元素通常是刚刚插入到数组中的，并且可能违反了堆的性质（即子节点的值可能小于其父节点的值）。

• parent 变量用于存储当前 child 元素的父节点索引。
• 循环会一直执行，直到 child 元素不再违反堆的性质或者 child 元素已经是根节点（此时 child 为 0）。
• 如果子节点的值小于父节点的值，那么通过 Swap 函数交换这两个元素的位置，并更新 child 和 parent 以继续进行比较。

HeapPush 函数用于将一个新元素 x 插入到堆 hp 中，并保持堆的性质。

• 首先，使用 assert 确保传入的 Heap 结构体指针 hp 不是 NULL。
• 如果当前堆的 _size 等于 _capacity，意味着堆已经满了，需要扩展空间。通过 realloc 函数为数组分配新的更大的空间。新的空间大小是当前容量的两倍或至少为 4（如果数组尚未分配空间）。
• 如果 realloc 失败，会打印错误并退出程序。
• 将新元素 x 插入到数组的末尾，即索引 hp->_size 处，并增加 _size。
• 最后，调用 AdjustUp 函数来调整堆，确保插入新元素后的堆仍然满足最小堆的性质。

删除数据（小堆）

数据的删除的逻辑这里我们不能--，或者++什么的，这些会导致堆变的不是堆

所以我们需要的是逻辑：

1，数组的首元素和尾元素进行交换

2，删除尾元素

3，首元素向下调整（这里看清楚了，这里是选取最小的数值进行交换）

代码实现

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	//我们假设左孩子的数值是最小的
	int chile = (parent * 2) + 1;
	while (chile < size)
	{
		//我们需要判断，右孩子是不是存在,并且筛选出最小的数值
		if (chile + 1 < size && a[chile] > a[chile + 1])
		{
			++chile;
		}
		//交换条件
		if (a[chile] < a[parent])
		{
			Swap(&a[chile], &a[parent]);
			parent = chile;
			chile = (chile * 2) + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	//首先删除之前不能为null
	assert(hp && hp->_size > 0);
	//删除我们删除的是堆头元素，删除尾部是没有意义的
	//1,进行交换
	//2，删除尾部
	//3，向下排序
	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	//传递的参数分别是，数组的头，头下标（parent是需要变化的，所以需要传递一个参数）
	AdjustDown(hp->_a, hp->_size, 0);
}

AdjustDown 函数用于在堆中移除根节点后，重新调整堆以保持堆的性质。它接收一个数组 a，数组的当前大小 size，以及需要向下调整的节点的父节点索引 parent。

• child 变量用于存储当前 parent 节点的左孩子的索引。
• 循环会一直执行，直到 child 变量超出数组的边界或者当前节点不再违反堆的性质。
• 如果右孩子存在且右孩子的值小于左孩子的值，那么将 child 更新为右孩子的索引。
• 如果子节点的值小于父节点的值，那么通过 Swap 函数交换这两个元素的位置，并更新 parent 和 child 以继续进行比较。

HeapPop 函数用于从堆中移除根节点（即堆顶元素），这通常是堆中最大或最小的元素。这个函数适用于最大堆或最小堆，具体取决于堆的性质。

• 首先，使用 assert 确保传入的 Heap 结构体指针 hp 不是 NULL，并且堆中至少有一个元素。
• 将堆顶元素（索引 0）与最后一个元素交换位置。这样做的原因是，移除最后一个元素的成本较低，因为它不需要调整堆。
• 减少 _size，表示堆中的元素数量减少了一个。
• 调用 AdjustDown 函数，传入数组的头部、新的堆大小和根节点索引（0），以调整堆并保持堆的性质。

取堆顶的数据（小堆）

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

1. 参数接收：函数接收一个指向 Heap 结构体的指针 hp。

2. 断言检查：

   • assert(hp);：确保传入的 hp 不是 NULL。如果 hp 是 NULL，assert 将触发断言失败，这通常会导致程序终止。
   • assert(hp->_size > 0);：确保堆不为空（即 _size 大于 0）。如果 _size 不大于 0，说明堆为空，此时没有元素可以返回，assert 同样会触发断言失败。

3. 返回堆顶元素：

   • return hp->_a[0];：返回位于数组 _a 第一个元素的值，这个元素在堆的表示中对应堆顶元素。

堆的数据个数（小堆）

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

1. 参数接收：函数接收一个指向 Heap 结构体的指针 hp。

2. 断言检查：

   • assert(hp);：确保传入的 hp 不是 NULL。如果 hp 是 NULL，assert 将触发断言失败，这通常会导致程序终止。

3. 返回元素数量：

   • return hp->_size;：返回 Heap 结构体中的 _size 成员的值。_size 成员表示堆中当前存储的数据元素的数量。

堆的判空（小堆）

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

1. assert(hp);：这行代码使用 assert 宏来确保传入的 hp 不是 NULL。如果 hp 是 NULL，assert 将触发一个断言失败，这通常会导致程序终止。assert 是一种运行时检查，用于调试目的，确保代码的正确性。

2. return hp->_size == 0;：这行代码返回 hp 指向的 Heap 结构体的 _size 成员是否等于 0。_size 成员表示堆中元素的数量。如果 _size 等于 0，表示堆中没有任何元素，函数返回 1（在 C 语言中，非零值被视为真），表示堆为空。如果 _size 不等于 0，函数返回 0，表示堆不为空。

堆的实现代码（小堆）

#include"Heap.h"
//堆的初始化
void HeapInit(Heap* hp)
{
	//初始化这里不开辟空间
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	//这里不需要循环释放，因为这里是数组实现堆的
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int chile)
{
	//获取父母所在位置
	int parent = (chile - 1) / 2;
	while (chile > 0)//这个循环条件不会越界，其余两个循环条件都会导致越界，但是也会正常运行
	{
		if (a[chile] < a[parent])
		{
			//传递地址，指针接收
			Swap(&a[chile], &a[parent]);
			//更新父母和孩子的下标
			chile = parent;
			parent = (chile - 1) / 2;
		}
		else
		{
			break;
		}
	}
 
	这个循环条件产生了越界，但是	printf("%d ", ps._a[-1]);（特别大） printf("%d ", ps._a[100]);（特别小）
	//while (a[chile] < a[parent])
	//{
	//	//传递地址，指针接收
	//	Swap(&a[chile], &a[parent]);
	//	//更新父母和孩子的下标
	//	chile = parent;
	//	parent = (chile - 1) / 2;
	//}
}
 
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断空间大小，并且开辟空间
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_a == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("HeapPush:tmp:");
			exit(1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	//插入
	hp->_a[hp->_size] = x;
	hp->_size++;
	//向上调整
	AdjustUp(hp->_a, hp->_size - 1);
}
//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	//我们假设左孩子的数值是最小的
	int chile = (parent * 2) + 1;
	while (chile < size)
	{
		//我们需要判断，右孩子是不是存在,并且筛选出最小的数值
		if (chile + 1 < size && a[chile] > a[chile + 1])
		{
			++chile;
		}
		//交换条件
		if (a[chile] < a[parent])
		{
			Swap(&a[chile], &a[parent]);
			parent = chile;
			chile = (chile * 2) + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	//首先删除之前不能为null
	assert(hp && hp->_size > 0);
	//删除我们删除的是堆头元素，删除尾部是没有意义的
	//1,进行交换
	//2，删除尾部
	//3，向下排序
	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	//传递的参数分别是，数组的头，头下标（parent是需要变化的，所以需要传递一个参数）
	AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp && hp->_size > 0);
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{ 
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}
 

堆的实现代码（大堆）

 
大堆
//堆的初始化
void HeapInit(Heap* hp)
{
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_capacity = hp->_size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上排序
void AdjustUp(HPDataType* a ,int chile)
{
	int parent = (chile - 1) / 2;
	while (chile > 0)
	{
		if (a[chile] > a[parent])
		{
			Swap(&a[chile], &a[parent]);
			chile = parent;
			parent= (chile - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	if (hp->_capacity == hp->_size)
	{
		int new_capacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * new_capacity);
		if (tmp == NULL)
		{
			perror(" ");
			exit(1);
		}
		hp->_capacity = new_capacity;
		hp->_a = tmp;
	}
	//插入数值
	hp->_a[hp->_size] = x;
	hp->_size++;
 
	//向上排序
	//首元素地址，孩子所在地址
	AdjustUp(hp->_a, hp->_size - 1);
}
//向下调整（大堆）
void AdjustDown(HPDataType* a, int n, int parent)
{
	int chile = parent * 2 + 1;
	//循环条件不能是父亲，不然会导致越界
	while (chile < n)
	{
		//三个孩子进行比较
		if (chile + 1 < n && a[chile] < a[chile + 1])
		{
			chile++;
		}
 
		if (a[chile] > a[parent])
		{
			Swap(&a[chile], &a[parent]);
			parent = chile;
			chile = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	//数值的长度，和父亲下标
	AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp && hp->_size > 0);
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{ 
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}
 

堆排序问题

需要在数组里面进行排序，我们可以采取堆排序对其解决问题

版本1：

创建一个数组等大的堆，把数组里面的数值输入到堆里面进行堆排序，但是这样的弊端就是，不是顺序排序

版本2：

每次我们取堆顶然后打印，最后出堆，循环

弊端就是这样是时间复杂度我们发现还是o(n)，没有必要那么麻烦半天时间复杂度还是这样

版本3:（推荐）

在数组上面进行排序，直接输出顺序排序

逻辑讲解

1，需要在数组里面进行排序，我们可以采取在数组建堆

2，然后交换收尾元素，每次调整的数值减少1

讲解逻辑

首先我们需要知道，

如果我们需要排序的是降序，我们就需要建立小堆

如果我们需要排序的是升序，我们就需要建立大堆

如果我们需要的是升序建立小堆的话

如果我们采取相反的方式的话，就会导致：（出现两个根）

首先n个数建小堆，固定第一个值是最小值
剩下的n-1个数再建堆
效率就很差了

如果相反的话，会导致根节点变化，从而导致逻辑混乱，数组里面的数值少的时候是不明显的，但是多的时候就不行了

逻辑实现图解

代码实现

//向下调整（大堆）
void AdjustDown(HPDataType* a, int n, int parent)
{
	int chile = parent * 2 + 1;
	//循环条件不能是父亲，不然会导致越界
	while (chile < n)
	{
		//三个孩子进行比较
		if (chile + 1 < n && a[chile] < a[chile + 1])
		{
			chile++;
		}
 
		if (a[chile] > a[parent])
		{
			Swap(&a[chile], &a[parent]);
			parent = chile;
			chile = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排序数组内进行调整解决
void sort_test(int* a, int sz)
{
	//放出来的是小堆，所以我们只能排序降序，这样逻辑更融洽
	//建堆
	for (int i = 0; i < sz; i++)
	{
		AdjustUp(a, i);
	}
	//交换排序 把首个元素和最后一个交换进行排序 每次--
	while (sz > 0)
	{
		Swap(&a[0], &a[sz - 1]);
		AdjustDown(a, sz - 1, 0);
		sz--;
	}
}

这个 sort_test 函数实现了一个堆排序算法，它接收一个整数数组 a 和它的大小 sz：

1. 建堆：首先，函数通过调用 AdjustUp 函数来构建一个小顶堆（最小堆）。建堆过程是从最后一个非叶子节点开始向上调整，直到堆顶。

2. 交换和排序：在建堆之后，函数进入一个循环，每次循环中，它将堆顶元素（当前堆中的最小元素）与当前堆的最后一个元素交换。然后，堆的大小减少 1，并且对剩余的堆进行向下调整以保持最小堆性质。

3. 循环结束：循环继续进行，直到堆的大小减小到 0。最终，数组 a 将被排序为降序。

top_k问题

top_k问题时间复杂度的计算

这里提前说明，时间复杂度的计算的目的是来计算向上调整的更优还是向下调整更优，从肉眼看的话向下调整优于向上调整，接下来我们进行时间复杂度的计算。

此时我们会用到等比数列求和以及裂项相消

如图

首先我们假设求的是满二叉树，我们求节点的个数

满二叉树节点个数

建堆问题：

建堆的话往往的倒数第一个非叶子结点建堆，会时间复杂度最优解：也就是

在构建堆（尤其是二叉堆）时，从最后一个非叶子节点开始进行调整是时间复杂度最优解的原因是，这种方法可以减少不必要的调整操作。

为什么从最后一个非叶子节点开始？

1. 叶子节点：在完全二叉树中，叶子节点不包含任何子节点，因此不需要进行调整。

2. 非叶子节点：从最后一个非叶子节点开始，向上逐个进行调整，可以确保每个节点在调整时，其子树已经是堆结构。这样可以减少调整的深度，因为每个节点最多只需要与其子节点交换一次。

3. 减少调整次数：如果从根节点开始调整，那么每个节点可能需要多次调整才能达到堆的性质，特别是那些位于树底部的节点。而从底部开始，每个节点只需要调整一次即可。

时间复杂度分析

构建堆的过程涉及对每个非叶子节点进行调整。对于一个具有

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/664856