手撕二叉树--堆的接口实现（附源码+图解）

堆的接口实现（附源码+图解）

文章目录

  • 堆的接口实现（附源码+图解）
  • 前言
  • 一、定义结构体
  • 二、接口实现（附图解+源码）
      • 1.初始化堆
      • 2.销毁堆
      • 3.尾插数据
        • （1）向上调整
        • （2）交换函数
        • （3）向下调整
      • 4.打印数据
      • 5.判断是否为空
      • 6.节点个数
      • 7.堆顶数据
      • 8.删除堆顶的数据
  • 三、源代码展示
    • （1）Heap.h（接口函数的声明）
    • （2）Heap.c（接口函数的实现）
    • （3）test.c（测试+主函数）
  • 总结

前言

本文主要介绍二叉树中堆的增删查改等接口实现，结尾附总源码！

一、定义结构体

在这里插入图片描述

代码如下（示例）：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a; //定义数组二叉树
	int size;      //二叉树结点个数
	int capacity;  //二叉树容量（考虑增容）
}HP;

二、接口实现（附图解+源码）

在这里插入图片描述
这里一共11个接口，我会我都会一 一为大家讲解（图解+源码）

1.初始化堆

由于二叉树中堆的存储结构是数组，所以初始化和销毁两个接口和顺序表等数据结构一样这里不做过多介绍！

代码如下（示例）：

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

2.销毁堆

代码如下（示例）：

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}

3.尾插数据

在这里插入图片描述

代码如下（示例）：

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
}

这里要注意：无论是大堆还是小堆都要满足 父亲结点 > or < 孩子结点（二叉树性质），这里我们采用向上下调整！push数据时只改变这条路径上的数据！
在这里插入图片描述

（1）向上调整

假设我们在插入几个数据之后，如下图！向上调整只会改变一条路径！！！
在这里插入图片描述

向上调整可以转变为 父亲结点一定大于孩子结点

在这里插入图片描述

在这里插入图片描述

代码如下（示例）：

void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

（2）交换函数

在进行函数传参的时候，形式参数是实际参数的一份临时拷贝，所以要传指针！

代码如下（示例）：

void Swap(HPDataType * px, HPDataType * py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

（3）向下调整

在这里插入图片描述

注意参数这里： 表示 从 parent结点 到 n结点 之间所有结点的算法，最高点是最小值
在这里插入图片描述

在这里插入图片描述

向下调整需要保证，top（最高结点）为最小值！
在这里插入图片描述

在这里插入图片描述

4.打印数据

由于二叉树存储结构是数组，打印的时候直接遍历即可！

代码如下（示例）：

void HeapPrint(HP* hp)
{
	for (int i = 0; i < hp->size; ++i)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

5.判断是否为空

代码如下（示例）：

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

6.节点个数

代码如下（示例）：

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

7.堆顶数据

不要忘记对数组进行判空操作，否则会出现野指针问题！

代码如下（示例）：

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}

8.删除堆顶的数据

这里要注意：在我们删除完数据之后要保护堆的性质结构(Adjustdown)。
在这里插入图片描述

在这里插入图片描述

三、源代码展示

（1）Heap.h（接口函数的声明）

代码如下（示例）：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void AdjustUp(int* a, int child);//向上调整
void AdjustDown(int* a, int n, int parent);//向下调整
void Swap(HPDataType* px, HPDataType* py);//交换
void HeapInit(HP* hp);//初始化堆
void HeapDestroy(HP* hp);//销毁堆
void HeapPush(HP* hp, HPDataType x);//尾插数据
void HeapPop(HP* hp);//删除堆顶的数据
HPDataType HeapTop(HP* hp);//取堆顶的数据
void HeapPrint(HP* hp);//打印堆（数组）
bool HeapEmpty(HP* hp);//判断堆是否为空
int HeapSize(HP* hp);//堆结点个数

（2）Heap.c（接口函数的实现）

代码如下（示例）：

#include "Heap.h"
void Swap(HPDataType * px, HPDataType * py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}
void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPrint(HP* hp)
{
	for (int i = 0; i < hp->size; ++i)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}
bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}
int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}
HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中小的那一个
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		// 如果小的孩子小于父亲，则交换，并继续向下调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 删除堆顶的数据
void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

（3）test.c（测试+主函数）

代码如下（示例）：

#include"Heap.h"
void TestHeap()
{
	int a[] = { 70, 56, 30, 25, 15, 10, 75 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapDestroy(&hp);
}

总结

以上就是今天要讲的内容，本文介绍二叉树中堆的接口实现（附图解和源码）！
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！
在这里插入图片描述

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

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

相关文章

Elasticsearch 需要了解的都在这

Elasticsearch 需要了解的都在这

ES选主过程&#xff1f;其实ES的选主过程其实没有很高深的算法加持&#xff0c;启动过程中对接点的ID进行排序&#xff0c;取ID最大节点作为Master节点&#xff0c;那么如果选出来的主节点中存储的元信息不是最新的怎么办&#xff1f;其实他是分了2个步骤做这件事&#xff0c;先…
阅读更多...
es-head插件插入查询以及条件查询（五）

es-head插件插入查询以及条件查询（五）

es-head插件插入查询以及条件查询 1.es-head插件页面介绍 页面详细介绍 2.es-head查询语句 2.1.查询索引中的全部数据 curl命令交互&#xff0c;采用GET请求 语法格式&#xff1a; curl -XGET es地址:9200/索引名/_search?pretty [rootelaticsearch ~]# curl -XGET 192…
阅读更多...
Mac环境变量配置（Java）

Mac环境变量配置（Java）

1.打开终端&#xff1a; 2.输入命令&#xff1a;【/usr/libexec/java_home -V】,查看默认的jdk下载地址&#xff08;绿色下划线的就是jdk默认路径&#xff09;&#xff08;注意⚠️&#xff1a;命令行终端是区分大小写的【-v 是不对的&#xff0c;必须是大写 -V】&#xff09; …
阅读更多...
Windows Server 2016远程桌面配置全过程

Windows Server 2016远程桌面配置全过程

镜像下载 系统镜像网址 本次下载的是 Windows Server 2016 (Updated Feb 2018) (x64) - DVD (Chinese-Simplified) 远程桌面配置 Step 1 在开始菜单搜索服务&#xff0c;打开服务器管理器&#xff0c;点击右上角的管理按钮 Step 2 添加角色控制&#xff0c;点击下一步 S…
阅读更多...
静态路由+DHCP实验（四路由器八PC）

静态路由+DHCP实验（四路由器八PC）

一.200.1.1.0/24子网划分 1.划分八个子网 2.选用前5个&#xff0c;第五个子网再划分4个子网作为骨干 二.规划路由 三.配置&#xff08;下一跳&#xff09; 1.先依次实现四个路由器之间全网可通 2.为路由器配置地址池&#xff0c;使用全局模式获取dhcp&#xff0c;指定网关…
阅读更多...
Springboot是什么

Springboot是什么

目录 为什么会要用springboot 1、之前 2、现在 springboot优点 springboot四大核心 自动装配介绍 1、自动装配作用是什么 2、自动装配原理 springboot starter是什么 1、starter作用 2、比如&#xff1a;我们想搭建java web框架 3、starter原理 SpringBootApplica…
阅读更多...
Endor Labs：2023年十大开源安全风险

Endor Labs：2023年十大开源安全风险

近日&#xff0c;Endor Labs发布了一份新报告&#xff0c;确定了2023年的十大开源安全风险。报告显示&#xff0c;许多软件公司依赖于开源软件代码&#xff0c;但在如何衡量和处理与开源软件相关的风险和漏洞方面缺乏一致性。调查发现&#xff0c;在应用程序中超过80%的代码可能…
阅读更多...
Go 结构体

Go 结构体

目录 什么是结构体 定义结构体 基本的方式实例化结构体 访问结构体的成员变量 指针类型的方式实例化结构体 取结构体地址的方式实例化 知识扩展&#xff1a;*号 和 &号 构造函数 成员函数&#xff08;成员方法&#xff09; 匿名成员变量 方法传入指针类型的结构…
阅读更多...
Mac M1通过VMWare Fusion安装Centos7记录(镜像和网络有大坑)

Mac M1通过VMWare Fusion安装Centos7记录(镜像和网络有大坑)

以前用linux系统基本都在我的服务器上或者是在win上进行&#xff0c;从没有在M1上进行创建&#xff0c;因此走了一些坑吧&#xff0c;这里会列出我的详细安装步骤。 下载镜像 镜像的下载网站&#xff1a;https://www.centos.org/download/ 在该网站中&#xff0c;不管是Every…
阅读更多...
多级评论单表结构设计

多级评论单表结构设计

这里的多级&#xff0c;本质上其实也就二级&#xff0c;例如微博的评论&#xff0c; 一级评论&#xff1a; 对微博的评论 二级评论&#xff1a; 对微博下的评论的回复评论 &#xff0c;这里包括二种 1. 回复的是一级评论&#xff0c; 2, 回复的是二级评论 效果如下 表数据 查…
阅读更多...
基于微信小程序的图书馆选座系统源码

基于微信小程序的图书馆选座系统源码

开发环境及工具&#xff1a; 大等于jdk1.8&#xff0c;大于mysql5.5&#xff0c;idea&#xff08;eclipse&#xff09;&#xff0c;微信开发者工具 技术说明&#xff1a; springboot mybatis 小程序 代码注释齐全&#xff0c;没有多余代码&#xff0c;适合学习&#xff08;…
阅读更多...
Android Studio模拟器运行无反应

Android Studio模拟器运行无反应

当Android Studio模拟器点击运行无反应 报以下错误&#xff1a; Emulator: PANIC: Cannot find AVD system path. Please define ANDROID_SDK_ROOT 问题分析 大多是由于默认路径带有中文&#xff0c;所以找不到 解决方法 1&#xff0c;删除镜像 2&#xff0c;配置环境变量 …
阅读更多...
Unity强化学习之ML-Agents的使用

Unity强化学习之ML-Agents的使用

Github下载链接&#xff1a;https://github.com/Unity-Technologies/ml-agents ML-Agents是游戏引擎Unity3D中的一个插件&#xff0c;也就是说&#xff0c;这个软件的主业是用来开发游戏的&#xff0c;实际上&#xff0c;它也是市面上用得最多的游戏引擎之一。而在几年前随着人…
阅读更多...
Maven配置—idea版

Maven配置—idea版

在java开发中&#xff0c;maven是个不可或缺的工具&#xff0c;可以简单理解成maven是个仓库&#xff0c;可以远程下载各种需要的插件&#xff0c;而且对于项目的打包编译等也非常简单&#xff1b;下面来说说如何配置maven 1. 首先下载maven的工具包&#xff0c;解压之后放在D…
阅读更多...
OCR之论文笔记TrOCR

OCR之论文笔记TrOCR

文章目录TrOCR: Transformer-based Optical Character Recognition with Pre-trained Models一. 简介二. TrOCR2.1. Encoder2.2 Decoder2.3 Model Initialiaztion2.4 Task Pipeline2.5 Pre-training2.6 Fine-tuning2.7 Data Augmentation三. 实验3.1 Data3.2 Settings3.2 Resul…
阅读更多...
测试用例设计指南

测试用例设计指南

作者&#xff1a;京东物流 王玉坤 软件测试设计是测试过程中重要的测试活动&#xff0c;怎么样设计测试用例能提高我们测试的效率和质量&#xff0c;从以下几个方面做了简单的讲解。 1 测试用例设计原则 测试用例设计的基本原则包括&#xff1a;有效性、清晰性、可复用性、可维…
阅读更多...
Linux 0.11

Linux 0.11

调试介绍 Linux 0.11-调试 Linux 最早期的代码-36 启动跟踪 BIOS 加载 电脑启动&#xff0c;CPU指向0xFFFFFFF0处&#xff0c;这里正好是系统ROM BIOS存放的地址。即开始执行BIOS指令。为了保持向下兼容&#xff0c;就会把与原PC兼容的BIOS代码和数据复制到低端1M末端的64K…
阅读更多...
0基础实现微信推送天气，生日等（女朋友快乐眼）

0基础实现微信推送天气，生日等（女朋友快乐眼）

最近微信小程序推送的功能很火&#xff0c;我也是去看了很多攻略&#xff0c;最后选了一个0基础的版本&#xff0c;最后也是实现了推送功能&#xff0c;如图 如何实现&#xff1f; 首先&#xff0c;打开微信官方提供的一个接口生成网址&#xff0c;微信扫码登录&#xff0c;然…
阅读更多...
数据挖掘（作业汇总）

数据挖掘（作业汇总）

目录 环境配置 实验1 数据 作业2 环境配置 实验开始前先配置环境 以实验室2023安装的版本为例&#xff1a; 1、安装anaconda&#xff1a;&#xff08;anaconda自带Python,安装了anaconda就不用再安装Python了&#xff09; 下载并安装 Anaconda3-2022.10-Windows-x86_64.ex…
阅读更多...
剑指offer JZ77 按之字形顺序打印二叉树

剑指offer JZ77 按之字形顺序打印二叉树

Java JZ77 按之字形顺序打印二叉树 文章目录Java JZ77 按之字形顺序打印二叉树一、题目描述二、双栈法三、队列reverse()法使用双栈法和队列reverse()法解决剑指offer JZ77 按之字形顺序打印二叉树的问题。 一、题目描述 给定一个二叉树&#xff0c;返回该二叉树的之字形层序遍…
阅读更多...
最新文章

Copyright @ 2022~2023