【数据结构初阶】二叉树--堆(顺序结构实现)

如果有一个关键码的集合K={k1，k2,，k3，...，k（n-1）}，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：Ki <= K(2*i+1)（Ki >= K(2*i+1) 且 Ki >= K(2*i+2)），i = 0，1，2...，则称为小堆（或大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

小堆：父结点不大于孩子结点；大堆：父结点不小于孩子结点。

数组不一定是有序地。小堆堆顶是堆的最小值，大堆堆顶是堆的最大值。

1.2 堆及二叉树的性质

堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。

二叉树的性质

对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为 i 的结点有：

若 i > 0，i 位置结点的双亲序号：（ i - 1）/ 2；i = 0，i 为根结点编号，无双亲结点；
若 2i + 1 < n，左孩子序号：2i + 1，2i + 1 >= n 则无左孩子；
若 2i + 2 < n，右孩子序号：2i + 2，2i + 2 >= n 则无右孩子；

通俗点来讲，父结点i---> 左孩子：2i+1，右孩子：2i+2。

1.3 堆的实现

1.3.1 创建堆的结构

堆的底层结构是数组

//创建堆的结构
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size;//堆中有效数据的个数
int capacity;//堆的容量
}HP;

1.3.2 初始化和销毁

//初始化
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}

//销毁
void HPDestroy(HP* php)
{
assert(php);

 if(php->arr)
{
free(php->arr);
php->arr = NULL;
}

php->size = php->capacity = 0;

}

1.3.3 入堆+向上调整算法（创建一个小堆）

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

向上调整算法

先将元素插入到堆的末尾，即最后一个子结点之后；
插入之后如果堆的性质遭到破坏，将新插入结点顺着双亲结点往上调整到合适位置即可。

【举例，向上调整算法】

思路：新插入的数据作为子结点（child），找到新插入数据的父结点（parent=（child-1）/ 2）（上面二叉树的性质），父结点和子结点进行比较，若父结点大于子结点，数据交换，不大于则不交换。再找新的父结点和子结点，循环条件是 child>0，child不需要等于0，child等于0时为根结点，根结点没有父结点不需要发生交换。

void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

//入堆
void HPPush(HP* php, HPDataType x)
{
assert(php);

//判断空间是否充足
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc file!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}
//此时空间已经充足
    //我们应该清楚地知道，size是x的下标，size在数组中指向x这个元素
php->arr[php->size] = x;

//向上调整算法
AdjustUp(php->arr, php->size);

php->size++;
}

1.3.4 出堆+向下调整算法（小堆）

堆的删除（出堆）

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据进行交换，然后删除数组最后一个数据，再进行向下调整算法。

向下调整算法有一个前提：左右子树必须是一个堆，才能进行调整。

出堆

将堆顶元素与堆中最后一个元素进行交换；
删除堆中最后一个元素；
将堆顶元素向下调整到满足堆特性为止。

【向下调整算法】

思路：堆顶元素为父结点，找到左右孩子中最小的那个子结点与之比较，若父结点大于子结点，交换，不大于则不交换，不断找新的父结点和子结点，就这样循环，注意循环结束的条件。上代码，结合代码中的注释更好的理解。

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//找左右孩子中最小的
        //child + 1 < n , 保证不越界
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[parent] > arr[child])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

//出堆
void HPPop(HP* php)
{
assert(php && php->size);
    
Swap(&php->arr[0], &php->arr[php->size-1]);
php->size--;//删除掉最后一个数据(堆顶元素)

//向下调整算法
AdjustDown(php->arr, 0, php->size);

}

1.3.5 判空+取堆顶数据+堆中有效数据个数

//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
assert(php && php->size);

return php->arr[0];
}

//堆中有效数据的个数
int HPSize(HP* php)
{
assert(php);
return php->size;
}

二、顺序结构二叉树---源码

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//创建堆的结构
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size;//堆中有效数据个数
int capacity;//堆的容量
}HP;

//初始化
void HPInit(HP* php);

//销毁
void HPDestroy(HP* php);

//入堆
void HPPush(HP* php, HPDataType x);

//出堆
void HPPop(HP* php);

//判空
bool HPEmpty(HP* php);

//取堆顶数据
HPDataType HPTop(HP* php);

//堆中有效数据的个数
int HPSize(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

//初始化
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}

//销毁
void HPDestroy(HP* php)
{
assert(php);
if (php->arr)
{
free(php->arr);
php->arr = NULL;
}
}

void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;

while (child > 0)//不需要等于0，child等于0时为根结点，根结点没有父结点不需要发生交换
{
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

//入堆
void HPPush(HP* php,HPDataType x)
{
assert(php);

//判断空间是否充足
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc file!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}

//此时空间已经充足
php->arr[php->size] = x;

//向上调整算法
AdjustUp(php->arr, php->size);

php->size++;

}

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//找左右孩子中最小的
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[parent] > arr[child])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

//出堆
void HPPop(HP* php)
{
assert(php && php->size);

Swap(&php->arr[0], &php->arr[php->size-1]);
php->size--;

//向下调整算法
AdjustDown(php->arr, 0, php->size);

}

//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
assert(php && php->size);

return php->arr[0];
}

//堆中有效数据的个数
int HPSize(HP* php)
{
assert(php);
return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void test01()
{
HP hp;
HPInit(&hp);

int arr[] = { 1,3,5,7,4,10,8 };

for (int i = 0; i < 7; i++)
{
HPPush(&hp, arr[i]);
}

printf("堆中有效数据个数：%d\n", HPSize(&hp));

while (!HPEmpty(&hp))
{
printf("%d ", HPTop(&hp));
HPPop(&hp);
}



HPDestroy(&hp);


}

int main()
{

test01();
return 0;
}

完——

Relaxing Time!

————————————— 《星空物语》 —————————————

星空物语（电视剧《一起来看流星雨》主题曲） - 张翰/朱梓骁/魏晨/俞灏明 - 单曲 - 网易云音乐

我是云边有个稻草人

期待与你的下一次相遇——

原文地址：https://blog.csdn.net/lrq13965748542/article/details/141711829

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【微服务】springboot 自定义注解+反射+aop实现动态修改请求参数
下一篇：如何在Windows和Mac上免费提取RAR文件？这里有方法

集成Sleuth实现链路追踪
【代码】集成Sleuth实现链路追踪。
阅读更多2025-01-24
Nuxt：利用public-ip这个npm包来获取公网IP
Nuxt：利用public-ip这个npm包来获取公网IP
阅读更多2025-01-24
【Linux】文件操作、系统IO相关操作、inode和输入输出重定向
文件在磁盘里，磁盘是永久性存储介质，因此文件在磁盘上的存储是永久性的，磁盘是外设（即是输出设备也是输入设备），对磁盘上所有文件的操作本质都是对外设的输入和输出，简称IO
阅读更多2025-01-24
10个非常基础的 Javascript 问题
根据MDN，JavaScript（通常缩写为JS）是一种轻量级的，解释性的，面向对象的语言，具有一流的功能，并且最著名的是Web页面的脚本语言，但它也用于许多非浏览器环境中。所有声明（函数，var，l
阅读更多2025-01-24
分布式与微服务：构建现代应用的关键架构
分布式系统和微服务架构是现代计算机系统的重要组成部分，它们为构建高可用、高可扩展和高性能的应用提供了强大的解决方案。通过上述 Java 示例，我们展示了不同场景下的实现方式，并深入探讨了其底层原理、性
阅读更多2025-01-24
青少年CTF练习平台 PHP的后门
根据提示，PHP/8.1.0-dev漏洞，修改请求头利用此漏洞。注意 zerodium后面拼接函数发送。
阅读更多2025-01-24
mock可视化&生成前端代码
介绍：mock是我们前后端分离的必要一环、ts、axios编写起来也很麻烦。我们就可以使用以下插件，来解决我们的问题。目前支持vite和webpack。欢迎小伙伴们提issues、我们共建。提升我们的
阅读更多2025-01-24
科比断腱之战所穿球鞋将被拍卖预计成交价会超过60万美元
虽然他在篮球运动方面有着得天独厚的天赋，但真正让他在竞争中脱颖而出的是他每天都坚持不懈地让自己变得更好。这双比赛穿的球鞋体现了他非凡的毅力，正是这种毅力使他成为史上最伟大的球员之一。在2013年4月1
阅读更多2025-01-24
分布式光纤应变监测是一种高精度、分布式的监测技术
主体结构应变监测：在高层建筑的混凝土柱、核心筒、梁等主要承重结构中安装分布式光纤应变传感器，能够实时监测建筑物在自身重力、风荷载、地震作用下的应变状态。例如，在高层建筑受到强风时，建筑物的迎风面和背风
阅读更多2025-01-24
30、Java中的异常(Exception)
自定义异常是开发者根据特定需求创建的异常类，它们通常继承自 Java 的 Exception 类或 RuntimeException 类。自定义异常使得异常处理更加灵活和具体，能够更好地描述程序中可能
阅读更多2025-01-24