二叉树——堆的实现

一.前言

前面我们讲解了二叉树的概念以及二叉树的存储结构：https://blog.csdn.net/yiqingaa/article/details/139224974?spm=1001.2014.3001.5502

今天我们主要讲讲二叉树的存储结构，以及堆的实现。

二.正文

1.二叉树的顺序结构及实现

1.1二叉树的顺序结构

 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

1.2堆的概念及结构

如果有一个关键码的集合K = { k₀，k₁，k₂ ，…，k_(n-1)(注意：_()在这里表示（）里是下标 ，如我们这里表示的是k的下标是n-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：K_(i) <=K_(2*i+1) 且K_(i) <=K_(2*i+2) (K_(i) >=K_(2*i+1) 且 K_(i)>=K_(2*i+2) ) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆的性质：

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

值得注意的是：这里我们虽然把它想像成树的形状，但其实我们的底层是数组，我们是通过改变数组，来控制这棵“树”的。

打个比方来说：蚂蚁上树这道菜，这盘菜里面真的有蚂蚁吗？其实没有，只不过是人为想像成的而已。在这里的二叉树也是同样的道理。

 2.堆的实现

2.1堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

这里我们给了一个数组。

int array[] = {27,15,19,18,28,34,65,49,25,37};

//向下调整算法
void AdjustDown(HPDataType* php,int n ,int parent )//php是数组指针
{
	int child = parent * 2 + 1;
	if (php[child] > php[child + 1])
		child = parent * 2 + 2;
	while (child < n)
	{
		if (php[child] < php[parent])
		{
			Swap(&(php[child]), &(php[parent]));
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.2向上调整算法

 现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向上调整算法可以把它调整成一个小堆。

我们给出了一个数组：

int array[] = {15,18,19,25,28,34,65,49,27,37，2};

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

2.3堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

void HPPush(HP* ps,HPDataType x)//堆尾插入数据，ps是我们堆指针
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;
		HPDataType* arr = (HPDataType*)realloc(ps->a,sizeof(HPDataType) * newcapacity);
		if (arr == NULL)
		{
			perror("realloc false");
			return;
		}
		ps->a = arr;
		ps->capacity = newcapacity;
	}
	ps->a[ps->size] = x;
	ps->size++;
	AdjustUp(ps->a,ps->size-1);
}

2.4堆的删除 

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

void HPPop(HP* ps)//删除堆顶数据
{
	assert(ps);
	assert(ps->size > 0);
	Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));
	ps->size--;
	AdjustDown(ps->a,ps->size,0);
}

3.堆代码的实现

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
};
typedef struct Heap HP;
void HPInit(HP* ps);//堆的初始化
void HPDestroy(HP* ps);//堆的删除

void HPPush(HP* ps, HPDataType x);//堆尾插入数据
void HPPop(HP* ps);//删除堆顶数据

HPDataType HPTop(HP* ps);//取出堆顶数据
bool HPEmpty(HP* ps);//判断堆是否为空

void Swap(HPDataType* a, HPDataType* b);//交换两个数据
void AdjustUp(HPDataType* php, int child);//向上调整算法
void AdjustDown(HPDataType* php, int n, int parent);//向下调整算法
int HPSize(HP* ps);//返回堆的有效数据个数
void HPSort(HPDataType* php, int n);//堆排序

Heap.c 

#include"Heap.h"
void HPInit(HP* ps)//堆初始化实现
{
	assert(ps);
	ps->a = NULL;
	ps->size = ps->capacity = 0;

}

void HPDestroy(HP* ps)//堆销毁实现
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void Swap(HPDataType* a,HPDataType* b)//两个数据的交换
{
	HPDataType tmp =*a;
	*a = *b;
	*b = tmp;
}

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

void HPPush(HP* ps,HPDataType x)//堆尾插入数据
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;
		HPDataType* arr = (HPDataType*)realloc(ps->a,sizeof(HPDataType) * newcapacity);
		if (arr == NULL)
		{
			perror("realloc false");
			return;
		}
		ps->a = arr;
		ps->capacity = newcapacity;
	}
	ps->a[ps->size] = x;
	ps->size++;
	AdjustUp(ps->a,ps->size-1);
}
void AdjustDown(HPDataType* php,int n ,int parent )//向下调整算法
{
	int child = parent * 2 + 1;
	if (php[child] > php[child + 1])
		child = parent * 2 + 2;
	while (child < n)
	{
		if (php[child] < php[parent])
		{
			Swap(&(php[child]), &(php[parent]));
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HPPop(HP* ps)//删除堆顶数据
{
	assert(ps);
	assert(ps->size > 0);
	Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));
	ps->size--;
	AdjustDown(ps->a,ps->size,0);
}
bool HPEmpty(HP* ps)//判断堆是否为空
{
	assert(ps);
	if (ps->size == 0)
	{
		return true;
	}
	return false;
}
HPDataType HPTop(HP* ps)//取出堆顶数据
{
	assert(ps);
	assert(ps->size > 0);
	return ps->a[0];
}
HPDataType HPSize(HP* ps)//返回堆有效数据个数
{
	assert(ps);
	return ps->size;
}
void HPSort(HPDataType* php,int n)//堆排序
{
	//降序 建小堆
	//升序 建大堆
	//建堆的第一种方法
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(php, i);
	}*/
	//建堆的第二种方法：
	for (int i = (n - 1 - 1) / 2; i < n; i++)//(n-1-1)/2是为了找最后一个数据的父亲
	{
		AdjustDown(php, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&(php[0]), &(php[end]));
		AdjustDown(php, end, 0);
		end--;
	}
}

test.c 

#include"Heap.h"
void test01()
{
	HP hp;
	HPInit(&hp);
	HPPush(&hp, 6);
	HPPush(&hp, 2);
	HPPush(&hp, 3);
	HPPush(&hp, 4);
	HPPush(&hp, 10);
	HPPush(&hp, 9);
	HPPush(&hp, 7);
	HPPop(&hp);
	printf("%d\n", HPTop(&hp));
	printf("%d\n", HPSize(&hp));
//	HPDestroy(&hp);
}
void test02()
{
	int arr[] = { 1,2,6,4,5,8,9,7 };
	HPSort(&arr,sizeof(arr)/sizeof(int));
}
int main()
{
	//test01();
	test02();
	return 0;
}

值得注意的是test.c是本人为了测试各函数是否正常而写出来的。

三.结言

 堆的分享就到这了。觉得对自己有帮助的同学，可不可以给个三连。

好啦，同学们我们下期再见，拜拜喽。

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

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

相关文章

手动操作很麻烦？试试这个自动加好友神器吧！

手动操作很麻烦？试试这个自动加好友神器吧！

你是不是也觉得手动逐一输入号码或是微信号&#xff0c;再搜索添加很麻烦&#xff1f;试试这个自动加好友神器——个微管理系统&#xff0c;帮助你省去繁琐的手工操作&#xff0c;节省时间和精力。 首先&#xff0c;在系统上登录微信号&#xff0c;无论你有多少个微信号&#…
阅读更多...
服务器重装系统与磁盘操作

服务器重装系统与磁盘操作

诱因&#xff1a;服务器原来装的EXSI&#xff0c;现在要重装一个ubuntu server&#xff0c;出现了下面一些问题&#xff0c;在此记录一下。 目录 1、过程中出现的问题&#xff08;2024.5.26&#xff09;1.1 问题1&#xff1a;如何磨掉原来的ESXI&#xff1f;1.2 问题2&#xf…
阅读更多...
【Typescript】通过变量的值即可获取变量的类型【typeof 变量】

【Typescript】通过变量的值即可获取变量的类型【typeof 变量】

注意&#xff1a;只要变量的类型准确,则typeof获取变量的类型就不会错 enum Test {a "a0",b "b0" }// 这里的a是一个变量的值 let a: Test.a "a0" as Test.a// 这里的typeof a是一个类型【Test.a】 let x: typeof a Test.a
阅读更多...
02 | 领域、子域、核心域、通用域和支撑域

02 | 领域、子域、核心域、通用域和支撑域

阅读更多...
玩转香橙派 AIpro，高性能AI开发板评测与项目案例分享

玩转香橙派 AIpro，高性能AI开发板评测与项目案例分享

公司最近刚忙完一个项目&#xff0c;闲暇之余&#xff0c;看着手里的树莓派、stm32、Esp32又有些手痒了&#xff0c;准备再搞点小项目出来&#xff0c;但一直没有什么好想法。 说来也巧&#xff0c;恰好收到了CSDN官方的OrangePi AIpro测评活动&#xff0c;平时一直都在用树莓…
阅读更多...
matplotlib---气泡图

matplotlib---气泡图

气泡图简介&#xff1a; 气泡图&#xff08;Bubble Chart&#xff09;是一种数据可视化图形&#xff0c;主要用于展示多个数据点之间的关系。 气泡图通过气泡的大小&#xff0c;位置和颜色可以展示数据之间的关系。在气泡图中&#xff0c;横轴和纵轴通常表示数据的两个维度&a…
阅读更多...
NoSQL Redis配置与优化

NoSQL Redis配置与优化

一、关系数据库与非关系型数据库 1. 关系型数据库&#xff1a; 关系型数据库是一个结构化的数据库&#xff0c;创建在关系模型&#xff08;二维表格模型&#xff09;基础上&#xff0c;一般面向于记录。 SQL 语句&#xff08;标准数据查询语言&#xff09;就是一种基于关系型…
阅读更多...
3d火灾救援模拟仿真培训软件复用性强

3d火灾救援模拟仿真培训软件复用性强

消防VR安全逃生体验系统是深圳VR公司华锐视点引入了前沿的VR虚拟现实、web3d开发和多媒体交互技术&#xff0c;为用户打造了一个逼真的火灾现场应急逃生模拟演练环境。 相比传统的消防逃生模拟演练&#xff0c;消防VR安全逃生体验系统包含知识讲解和模拟实训演练&#xff0c;体…
阅读更多...
（2024，基于熵的激活函数动态优化，具有边界条件的最差激活函数，修正正则化 ReLU）寻找更优激活函数

（2024，基于熵的激活函数动态优化，具有边界条件的最差激活函数，修正正则化 ReLU）寻找更优激活函数

A Method on Searching Better Activation Functions 公众号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 3. 动机 4. 方法论 4.1 问题设定 4.1.1 贝叶斯错误率和信息熵 4.1.2 激活…
阅读更多...
物业

物业

用户报修 审核专员可以操作&#xff08;前端&#xff09;&#x1f197; 工程部可以看到不可以操作&#xff08;前端&#xff09;&#x1f197; 项目经理可以看到不可以操作&#xff08;前端&#xff09;&#x1f197; 经理可以看到不可以操作&#xff08;前端&#xff09;&…
阅读更多...
Kivy 项目51斩百词 6 播放读音

Kivy 项目51斩百词 6 播放读音

为了给小喇叭图像绑定点击事件&#xff0c;实现当用户点击按钮时&#xff0c;触发该事件对应的回调方法。 在方法内对于不同的系统Kivy使用不同的播放语音方法&#xff0c; 对于Windows系统 使用SoundLoader播放语音&#xff0c; 对于其他的Unix系统 使用Pyjnjus播放…
阅读更多...
C语言 数组——排序算法的函数实现

C语言 数组——排序算法的函数实现

目录 交换法排序 用交换法对成绩数组升序排序 选择法排序 冒泡法排序 归并法排序 交换法排序 用交换法对成绩数组升序排序 选择法排序 冒泡法排序 归并法排序
阅读更多...
拼多多商品详情商品标题sku等信息抓取接口API调用步骤演示

拼多多商品详情商品标题sku等信息抓取接口API调用步骤演示

接口名称&#xff1a;item_get_app_pro 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称&#xff08;包括在请求地址中&#xff09;[item_search,item_get,item_search_sho…
阅读更多...
区块链技术引领：Web3时代的新网络革命

区块链技术引领：Web3时代的新网络革命

随着区块链技术的快速发展和不断成熟&#xff0c;人们已经开始意识到它所带来的潜在影响&#xff0c;尤其是在构建一个更加去中心化、安全和透明的互联网时。这个新的互联网时代被称为Web3&#xff0c;它将不再受制于传统的中心化平台&#xff0c;而是更多地依赖于去中心化的网…
阅读更多...
【C++】＜图形库＞ EasyX基础使用

【C++】＜图形库＞ EasyX基础使用

文章目录 一、安装EasyX库 二、图形窗口显示 三、基本绘图函数 四、图片显示 五、键盘交互 六、鼠标交互 七、双缓冲区解决闪屏 一、安装EasyX库 已经有兄弟写得很清楚了&#xff0c;见EasyX | 安装教程&#xff08;详细图文&#xff09;。 二、图形窗口显示 1. 包含的…
阅读更多...
uni-app 接入微信短剧播放器

uni-app 接入微信短剧播放器

前言 作为一个 uniapp 初学者&#xff0c;恰巧遇到微信短剧播放器接入的需求&#xff0c;在网上检索许久并没有发现傻瓜式教程。于是总结 uni-app 官网文档及微信开放文档&#xff0c;自行实践后&#xff0c;总结出几个步骤&#xff0c;希望为大家提供些帮助。实践后发现其实确…
阅读更多...
42.接雨水

42.接雨水

题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,…
阅读更多...
Linux基础知识点总结！超详细

Linux基础知识点总结！超详细

Linux 的学习对于一个IT工程师的重要性是不言而喻的&#xff0c;学好它是工程师必备修养之一。 Linux 基础 操作系统 操作系统Operating System简称OS&#xff0c;是软件的一部分&#xff0c;它是硬件基础上的第一层软件&#xff0c;是硬件和其它软件沟通的桥梁。 操作系统…
阅读更多...
抖音小店出单之后怎么发货？抖店详细发货流程来了

抖音小店出单之后怎么发货？抖店详细发货流程来了

大家好&#xff0c;我是喷火龙。 抖音小店发货是有规则的&#xff0c;如果出现超时发货或者虚假发货都会被平台处罚的&#xff0c;会影响我们店铺的评分和正常运营&#xff0c;还有些小伙伴们在发货的时候会遇到平台的违规提醒等问题。 今天我就给大家讲一下抖音小店的发货流…
阅读更多...
夏季天气炎热没胃口怎么办？没食欲，心情浮躁怎么调理？

夏季天气炎热没胃口怎么办？没食欲，心情浮躁怎么调理？

点击文末领取中医揿针的视频教程跟直播讲解 夏季天气炎热&#xff0c;很容易就让人出现胃口不佳的情况&#xff0c;再加上不少人需要长期服药&#xff0c;或是受到病痛困扰&#xff0c;更是严重影响了食欲。 夏养心 夏季&#xff0c;在这个季节&#xff0c;心脏的负担是很重…
阅读更多...
最新文章

Copyright @ 2022~2023