数据结构——二叉树2.0
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
✅<1>主页：我的代码爱吃辣
📃<2>知识讲解：数据结构——二叉树
🔥<3>创作者：我的代码爱吃辣
☂️<4>开发环境：Visual Studio 2022
💬<5>前言：上期讲了二叉树的相关概念今天来讲一下二叉树的顺序存储——堆。
目录
我们什么都没有唯一的本钱就是青春。梦想让我与众不同奋斗让我改变命运
📔一.二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
📕（1顺序结构
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
📖（2链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链以后学到高阶数据结构如红黑树等会用到三叉链。
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};💰二.二叉树的顺序存储结构的实现
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
堆的孩子和父亲下标关系：
🪙（1堆的概念及结构
堆是一个可以看成完全二叉树的数组对象在将它看成完全二叉树时候完全二叉树的每一个父亲结点的值总是大于（小于孩子结点的值我们称之为大堆（小堆或者大根堆（小根堆。
堆得性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
🍗（2堆的实现
🥞1.堆结构的定义初始化及销毁
由于堆是一个可以看成完全二叉树的数组对象所以在实现堆及其相关操作的时候实际上都是对顺序表的操作。
typedef struct Heap
{
HPDateType* a; //数据域
int size; //数据个数
int capacity; //容量
}Heap;//初始化
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}//堆的销毁
void HeapDestroy(Heap* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}🧇2.堆的插入
堆的插入需要保证插入以后还是一个堆所以这里用到了向上调整算法。
在数组中就是插入一个数在数组的尾上再通过向上调整算法调整到合适的位置。
在以堆的角度来看（小堆为例将新插入的值看作孩子与其父亲位置的值比较如果比父亲位置的值还要小那就将该值与父亲位置的值进行交换交换后将父亲位置当作新的孩子继续与其父亲位置的值比较这样一直向上比较并交换直到父亲位置的值比自己小或该位置已经没有父亲了调整结束。
代码：
//交换
void Swap(HPDateType* n1, HPDateType* n2)
{
HPDateType tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
//判断是否需要扩容
void JudgeCapacity(Heap*php)
{
assert(php);
if (php->capacity == php->size)
{
int newcaprcity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDateType* tmp = realloc(php->a, sizeof(HPDateType) * newcaprcity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
php->a = tmp;
php->capacity = newcaprcity;
}
}
//向上调整算法
void AdjustUp(HPDateType* a, int size, 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;
}
}
}
//堆的插入
void HeapPush(Heap* php, HPDateType x)
{
assert(php);
//判断时候需要扩容
JudgeCapacity(php);
//在数组的尾上插入数据
php->a[php->size++] = x;
//将新插入的数据进行向上调整
AdjustUp(php->a, php->size,php->size - 1);
}测试：
void Print(Heap* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
}
int main()
{
//定义
Heap hp;
//初始化
HeapInit(&hp);
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(array) / sizeof(array[0]);
//数组数据一次插入堆中
for (int i = 0; i < n; i++)
{
HeapPush(&hp, array[i]);
}
//打印堆的内容
Print(&hp);
//销毁堆
HeapDestroy(&hp);
return 0;
}
每一次插入都会经过一次向上调整最后生成的就是妥妥的小堆。
🧀3.堆的创建
下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。这里用到的就是向下调整算法。
向下调整算法（大堆为例:从第一个非叶子结点开始找到其孩子结点中较大的一个与父亲位置进行交换然后将孩子作为新的父亲再次比较和交换直到父亲结点比两个结点的值都大或者已经没有孩子了为止。
从第一个不为叶子的结点开始一次往前都进行向下调整最后得到的就是堆。
代码：
void Swap(HPDateType* n1, HPDateType* n2)
{
HPDateType tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
//向下调整算法(大堆)
void AdjustDown(HPDateType* arr,int n, int parent)
{
//找到第一个孩子
int child = parent * 2 + 1;
while (child < n)//求出的孩子已经超过数组下标的大小
{
//与第二个孩子比较大小
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
//与其父亲的值比较如果孩子的值比父亲大就交换
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
//将孩子作为新的父亲并找到新的孩子继续进行比较
parent = child;
child = parent * 2 + 1;
}
else//如果父亲的值比孩子的大此时以该父亲为根的完全二叉树已经是堆
{
break;
}
}
}
//对已经给出的数组进行建堆
void HeapCreate(Heap* php, HPDateType* arr, int n)
{
assert(php);
//初始化堆
php->a = (HPDateType*)malloc(sizeof(HPDateType) * n);
php->capacity = n;
php->size = n;
//数据拷贝到堆中
memmove(php->a,arr,sizeof(arr[0]) * n);
//找到第一个非叶子结点并依次向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, n,i);
}
}
测试：
void Print(Heap* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
}
int main()
{
//定义
Heap hp;
//初始化
HeapInit(&hp);
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(array) / sizeof(array[0]);
HeapCreate(&hp, array, n);
//打印堆的内容
Print(&hp);
//销毁堆
HeapDestroy(&hp);
return 0;
}
🥣4. 堆的删除：
堆的删除删除堆顶数据需要保证删除以后还是一个堆我们通常的做法就是将堆顶数据与堆的最后数据进行交换再将堆的数据个数减一为了保证删除以后还是一个堆再将堆顶数据进行向下调整。
代码:
//堆的删除删除堆顶数据并保证删除以后仍是堆
void HeapPop(Heap* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size]-1);
php->size--;
AdjustDown(php->a, php->size, 0);
}
测试：
void Print(Heap* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
int main()
{
//定义
Heap hp;
//初始化
HeapInit(&hp);
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(array) / sizeof(array[0]);
HeapCreate(&hp, array, n);
Print(&hp);
HeapPop(&hp);
Print(&hp);
HeapPop(&hp);
Print(&hp);
//销毁堆
HeapDestroy(&hp);
return 0;
}
🍿 5.拿到堆顶数据
//拿到堆顶数据
HPDateType HeapTop(Heap* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}🥗 6.堆的数据个数
//堆的数据个数
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
🍘7.堆的判空
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}🍙8.TopK问题
第一类TopK问题：
假如我们有一组数据现在的需求就是找这一组数据中的前k大的k个数。首先将数据建堆我们可以通过不断地从大堆里面选堆顶数据的数再将堆顶数据删除循环选出k个数这样选出来的就是前k大的k个数。
代码：
//topk问题
void HeapTopK(Heap* php, int k)
{
assert(php);
assert(k > 0);
for (int i = 0; i < k; i++)
{
printf("%d ", HeapTop(php));
HeapPop(php);
}
printf("\n");
}测试：
int main()
{
//定义
Heap hp;
//初始化
HeapInit(&hp);
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(array) / sizeof(array[0]);
HeapCreate(&hp, array, n);
//选出前3大的3个数据
HeapTopK(&hp, 3);
//销毁堆
HeapDestroy(&hp);
return 0;
}
第二类TopK问题：
上述的TopK问题有的小伙伴想到我们用一个排序也能解决问题呀为啥非要建堆呢？但是如果我们的数据量非常的大数据有100G大小存储在我们的磁盘里面此时我们再想寻选出TopK如果使用排序就需要把数据加载到内存中这个时候电脑的内存是不够加载的也就无法排序；日过我们使用堆我们只需要建可以容纳K个数据小堆每次从磁盘中读取一个数据读取的数据与堆顶数据比较去过比堆顶数据大就将该数据赋值到堆顶并将堆顶数据进行一次向下调整保证堆顶数据一直是堆中最小的。这里大家可以想象是打擂台。
注意：这里再选前K大的数的时候只能建小堆如果建大堆我们读取的第一个数就是最大并且放在了堆顶后面的数据就会被堵在外面堆中的数据就会无法更新。
代码:
//topk 文件大数据量
void TopK_File(int k)
{
//造数据,造1000个10000以下的随机数
FILE* pfile = fopen("test.txt", "w");
srand(time(0));
for (int i = 0; i < 1000; i++)
{
fprintf(pfile, "%d\n", rand() % 10000);
}
fclose(pfile);
//建小堆
Heap hp;
HeapInit(&hp);
int* arr = (int*)malloc(sizeof(arr[0]) * k);
for (int i = 0; i < k; i++)
{
arr[i] = INT_MIN;
}
HeapCreate(&hp, arr, k);
//topK 选数
FILE* pfile_ = fopen("test.txt", "r");
for (int i = 0; i < 1000; i++)
{
int tmp = 0;
fscanf(pfile,"%d", &tmp);
int hptop = HeapTop(&hp);
//文件中读取的数据与堆顶数据比较
if (tmp > hptop)
{
hp.a[0] = tmp;
AdjustDown(hp.a, k, 0);
}
}
fclose(pfile_);
Print(&hp);
HeapDestroy(&hp);
}测试：
int main()
{
//前5大的5个数据
TopK_File(5);
}
🍛三.时间复杂度分析：
🍡（1向上调整算法插入建堆的时间复杂苏分析：
🥟（2向下调整算法直接建堆的时间复杂苏分析：
🥡 四.堆排序
🍠（1排序思想
利用堆来排序主要有两个步骤：
1.建堆：排升序建大堆排降序建小堆
2.利用堆删除的思想经行排序
首先我们来针对排升序建大堆来解释一下我们知道大堆堆顶数据是最大数据如果我们将顶数据与最够一个数据进行交换这样我们就可以将最大的数放在了最后除去最后一个数据将其他数据按栈顶数据数据进行向下调整。依次这样就可以达到排序的效果。
🍱（2代码代码：
void HeapSort(int *arr,int n)
{
//建大堆选择时间复杂度比较小向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
//选数排序
int end = n - 1;
while (end)
{
//每次选出堆顶数据往后放
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
}🍥最后：
我们什么都没有唯一的本钱就是青春。梦想让我与众不同奋斗让我改变命运
