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

hello！

目录

一、实现顺序结构二叉树

1.1  堆的概念和结构

1.2  堆及二叉树的性质

1.3  堆的实现

1.3.1  创建堆的结构

1.3.2  初始化和销毁

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

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

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

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

Heap.h

Heap.c

test.c

Relaxing Time！

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

正文开始——

一、实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，分为大根堆（大堆）和小根堆（小堆），具有二叉树的特性的同时，还具备其他的特性。

1.1  堆的概念和结构

如果有一个关键码的集合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 的结点有：
  1.  若 i > 0，i 位置结点的双亲序号：（ i - 1）/ 2；i = 0，i 为根结点编号，无双亲结点；
  2. 若 2i + 1 < n，左孩子序号：2i + 1，2i + 1 >= n 则无左孩子；
  3. 若 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!

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

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

我是云边有个稻草人

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/872406.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2024Java基础总结+【Java数据结构】(2)

2024Java基础总结+【Java数据结构】(2)

面向对象07&#xff1a;简单小结类与对象 面向对象08&#xff1a;封装详解 面向对象09&#xff1a;什么是继承 ctrlh看类的关系&#xff0c;所有的类都默认的或间接继承Object 面向对象10&#xff1a;Super详解 super注意点: super调用父类的构造方法&#xff0c;必须在构造方…
阅读更多...
OCR经典神经网络(一)文本识别算法CRNN算法原理及其在icdar15数据集上的应用

OCR经典神经网络(一)文本识别算法CRNN算法原理及其在icdar15数据集上的应用

OCR经典神经网络(一)文本识别算法CRNN算法原理及其在icdar15数据集上的应用 文本识别是OCR&#xff08;Optical Character Recognition&#xff09;的一个子任务&#xff0c;其任务为&#xff1a;识别一个固定区域的的文本内容。 在OCR的两阶段方法里&#xff0c;文本识别模型接…
阅读更多...
七，Spring Boot 当中的 yaml 语法使用

七，Spring Boot 当中的 yaml 语法使用

七&#xff0c;Spring Boot 当中的 yaml 语法使用 文章目录 七&#xff0c;Spring Boot 当中的 yaml 语法使用1. yaml 的介绍2. yaml 基本语法3. yaml 数据类型4. 学习测试的准备工作4.1 yaml 字面量4.2 yaml 数组4.3 yaml 对象 5. yaml 使用细节和注意事项6. 总结&#xff1a;…
阅读更多...
2024高教社杯数学建模竞赛解题思路

2024高教社杯数学建模竞赛解题思路

高教社杯数学建模竞赛解题思路&#xff1a;独家出版&#xff0c;思路解析模型代码结果可视化。 A题思路及程序链接&#xff1a;https://mbd.pub/o/bread/ZpqblJZs B题思路及程序链接&#xff1a;https://mbd.pub/o/bread/ZpqblJZx D题思路及程序链接&#xff1a;https://mbd.pu…
阅读更多...
常用排序算法（上）

常用排序算法（上）

目录 前言&#xff1a; 1.排序的概念及其运用 1.1排序的概念 1.2排序运用 1.3 常见的排序算法 2.常见排序算法的实现 2.1 堆排序 2.1 1 向下调整算法 2.1 2 建堆 2.1 3 排序 2.2 插入排序 2.1.1基本思想&#xff1a; 2.1.2直接插入排序&#xff1a; 2.1.3 插…
阅读更多...
elementUI——checkbox复选框监听不到change事件，通过watch监听来解决——基础积累

elementUI——checkbox复选框监听不到change事件，通过watch监听来解决——基础积累

今天在写后台管理系统的时候&#xff0c;遇到一个需求&#xff0c;就是要求监听复选框的change事件&#xff0c;场景就是&#xff1a;两个复选框互斥&#xff0c;且可以取消勾选。 就是这两个复选框可以同时都不勾选&#xff0c;如果勾选的话&#xff0c;另一个一定要取消勾选。…
阅读更多...
具身智能猜想 ——机器人进化

具身智能猜想 ——机器人进化

设想一个机器人进化的仿真模拟环境&#xff0c;可以通过 “基因突变” 产生新功能&#xff0c;让机器人逐步进化。以下是这个进化系统的关键要素和可能的实现步骤&#xff1a; 1. 仿真环境 虚拟世界&#xff1a;创建一个包含多样化任务和挑战的虚拟环境&#xff0c;如探索、抓…
阅读更多...
多智能体强化学习：citylearn城市建筑能量优化和需求响应

多智能体强化学习：citylearn城市建筑能量优化和需求响应

今天分享一个用于能量优化的强化学习框架&#xff0c;citylearn 代码量非常庞大&#xff0c;我都不敢看&#xff0c;看也看不完&#xff0c;不花一定的时间难以搞懂它的原理。 CityLearn&#xff08;CL&#xff09;环境是一个类似 OpenAI Gym 的环境&#xff0c;它通过控制不…
阅读更多...
UE5 C++ 读取图片插件(一)

UE5 C++ 读取图片插件(一)

原来UE可以使用 static,之前不知道&#xff0c;一用就报错。 static TSharedPtr<IImageWrapper> GetImageWrapperByExtention(const FString InImagePath); //智能指针&#xff0c;方便追寻引用C,加载ImageWrapperstatic UTexture2D* LoadTexture2D(const FString& …
阅读更多...
代码随想录 刷题记录-28 图论 (5)最短路径

代码随想录 刷题记录-28 图论 (5)最短路径

一、dijkstra&#xff08;朴素版&#xff09;精讲 47. 参加科学大会 思路 本题就是求最短路&#xff0c;最短路是图论中的经典问题即&#xff1a;给出一个有向图&#xff0c;一个起点&#xff0c;一个终点&#xff0c;问起点到终点的最短路径。 接下来讲解最短路算法中的 d…
阅读更多...
matter的Commissioning（入网过程）整体流程、加密方式、通信信息结构

matter的Commissioning（入网过程）整体流程、加密方式、通信信息结构

在Matter协议中&#xff0c;**控制器负责将新设备加入网络&#xff08;commissioning&#xff09;**的整个流程&#xff0c;这一过程包括设备的发现、验证、授权、加入Fabric&#xff0c;以及最终建立数据通信的步骤。配网完成后的数据通信过程同样遵循严格的加密方式&#xff…
阅读更多...
C语言 | Leetcode C语言题解之第385题迷你语法分析器

C语言 | Leetcode C语言题解之第385题迷你语法分析器

题目&#xff1a; 题解&#xff1a; struct NestedInteger* helper(const char * s, int * index){if (s[*index] [) {(*index);struct NestedInteger * ni NestedIntegerInit();while (s[*index] ! ]) {NestedIntegerAdd(ni, helper(s, index));if (s[*index] ,) {(*index…
阅读更多...
TCP的流量控制深入理解

TCP的流量控制深入理解

在理解流量控制之前我们先需要理解TCP的发送缓冲区和接收缓冲区&#xff0c;也称为套接字缓冲区。首先我们先知道缓冲区存在于哪个位置&#xff1f; 其中缓冲区存在于Socket Library层。 而我们的发送窗口和接收窗口就存在于缓冲区当中。在实现滑动窗口时则将两个指针指向缓冲区…
阅读更多...
社交媒体的智能变革：Facebook AI优化用户体验

社交媒体的智能变革：Facebook AI优化用户体验

Facebook作为全球领先的社交平台&#xff0c;一直致力于通过人工智能&#xff08;AI&#xff09;技术提升用户体验。AI技术在Facebook的应用涵盖了推荐系统、自然语言处理、广告投放和用户反馈等多个方面&#xff0c;使平台的互动和内容体验更加智能和个性化。 推荐系统的智能化…
阅读更多...
火焰传感器详解（STM32）

火焰传感器详解（STM32）

目录 一、介绍 二、传感器原理 1.原理图 2.引脚描述 三、程序设计 main.c文件 IR.h文件 IR.c文件 四、实验效果 五、资料获取 项目分享 一、介绍 火焰传感器是一种常用于检测火焰或特定波长&#xff08;760nm-1100nm&#xff09;红外光的传感器。探测角度60左右&am…
阅读更多...
高压喷雾车的功能与应用_鼎跃安全

高压喷雾车的功能与应用_鼎跃安全

在一次森林火灾中&#xff0c;位于山区的一个小型度假村附近突然起火&#xff0c;由于山风强劲&#xff0c;火势迅速蔓延&#xff0c;消防部门立即调派多辆高压喷雾车赶往现场。在扑救过程中&#xff0c;传统消防车难以进入崎岖的山路&#xff0c;但高压喷雾车凭借其高机动性顺…
阅读更多...
大模型笔记01--基于ollama和open-webui快速部署chatgpt

大模型笔记01--基于ollama和open-webui快速部署chatgpt

大模型笔记01--基于ollama和open-webui快速部署chatgpt 介绍部署&测试安装ollama运行open-webui测试 注意事项说明 介绍 近年来AI大模型得到快速发展&#xff0c;各种大模型如雨后春笋一样涌出&#xff0c;逐步融入各行各业。与之相关的各类开源大模型系统工具也得到了快速…
阅读更多...
【神经网络系列（高级）】神经网络Grokking现象的电路效率公式——揭秘学习飞跃的秘密【通俗理解】

【神经网络系列（高级）】神经网络Grokking现象的电路效率公式——揭秘学习飞跃的秘密【通俗理解】

【通俗理解】神经网络Grokking现象的电路效率公式 论文地址&#xff1a; https://arxiv.org/abs/2309.02390 参考链接&#xff1a; [1]https://x.com/VikrantVarma_/status/1699823229307699305 [2]https://pair.withgoogle.com/explorables/grokking/ 关键词提炼 #Grokkin…
阅读更多...
【办公效率】Axure会议室预订小程序原型图，含PRD需求文档和竞品分析

【办公效率】Axure会议室预订小程序原型图，含PRD需求文档和竞品分析

作品说明 作品页数&#xff1a;共50页 兼容版本&#xff1a;Axure RP 8/9/10 应用领域&#xff1a;中小型企业的会议室在线预订 作品申明&#xff1a;页面内容仅用于功能演示&#xff0c;无实际功能 作品特色 本作品为会议室预订小程序原型图&#xff0c;定位于拥有中大型…
阅读更多...
Python 人脸识别实战教程

Python 人脸识别实战教程

引言 在本教程中&#xff0c;我们将深入探讨如何使用Python和OpenCV库来实现人脸检测与识别。本文从基础知识入手&#xff0c;逐步构建一个简单的人脸识别系统。本教程假设读者已经熟悉Python编程&#xff0c;并具备一定的OpenCV使用经验。 环境配置 安装必要的库 确保您的…
阅读更多...
最新文章

Copyright @ 2022~2023