C语言数据结构之二叉堆

愿你千山暮雪

海棠依旧

不为岁月惊扰平添忧愁

🎥前期回顾-二叉树

🔥数据结构专栏

期待小伙伴们的支持与关注！！！

目录

前期回顾

二叉堆的概念及结构 

 二叉堆的创建

顺序表的结构声明

 顺序表的创建与销毁

二叉堆的插入 

 二叉堆显示堆顶元素

 二叉堆的删除

 二叉堆的判空

整体代码实现

前期回顾

二叉树的顺序结构 

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。而我们今天学的 堆 总是一棵 完全二叉树

作为一棵完全二叉树，二叉堆可以用一个1-n 的数组来存储

对于双亲节点p，p*2+1即为左孩子，p*2+2即为右孩子

对于孩子节点 child 求双亲结点 parent 即 parent = (child - 1) / 2

同时，用size记录当前二叉堆中节点的个数

顺序存储的结论

如果 i 为0，则 i 表示的节点为根节点，否则 i 节点的双亲节点为 (i - 1)/2
如果 2 * i + 1 小于节点个数，则节点 i 的左孩子下标为 2 * i + 1，否则没有左孩子
如果 2 * i + 2 小于节点个数，则节点 i 的右孩子下标为 2 * i + 2，否则没有右孩子

二叉堆（Binary Heap）是最简单、常用的堆，是一棵符合堆的性质的 完全二叉树

它可以实现 O(log⁡n) 的 插入 或 删除 某个值，并且 O(1) 地查询 最大（或最小）值

二叉堆的概念及结构 

概念#

堆在运用范围上：用来在一组变化频繁（发生增删查改的频率较高）的数据集中查找最值

堆在物理层面上：表现为一组连续的数组区间 long[ ] array 将整个数组看作是堆

堆在逻辑结构上：一般被视为是一颗完全二叉树

结构#

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

堆的性质#

堆中某个节点的值总是不大于或不小于其双亲节点的值
堆总是一棵完全二叉树
小根堆#

<1>双亲节点的值 小于或等于 子节点的值

大根堆#

<2>双亲节点的值 大于或等于 子节点的值

 二叉堆的创建

下面以 小根堆 进行演示

顺序表的结构声明

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

typedef int HeapDataType;

typedef struct Heap
{
	int size;
	int capacity;
	HeapDataType* data;
}HP;

 顺序表的创建与销毁

创建

void HPInit(HP* php)
{
	assert(php);
	php->data = NULL;
	php->capacity = php->size = 0;
}

销毁

void HPDestroy(HP* php)
{
	assert(php);
	free(php->data);
	php->data = NULL;
	php->capacity = 0;
	php->size = 0;
}

二叉堆的插入 

 顺序表的基本结构

void HPPush(HP* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* newNode = (HeapDataType*)realloc(php->data, sizeof(HeapDataType) * newcapacity);
		if (newNode == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		php->data = newNode;   
		php->capacity = newcapacity;
	}
	php->data[php->size] = x;
	php->size++;
	AdjustUp(php->data, php->size - 1);
}

交换函数 交换孩子与双亲之间的位置

void Swap(HeapDataType* n, HeapDataType* m)
{
	HeapDataType tmp = *n;
	*n = *m;
	*m = tmp;  
}

我们以下面这两颗树为例

如何 插入 元素，同时维护二叉堆的性质？

如果我们想在二叉堆中插入一个数 11 或者 10

我们可以采用上调算法：该子节点不断与双亲节点比较，如果比双亲节点 小 就与之交换

直到不大于双亲节点或成为根节点为止

上调算法

void AdjustUp(HeapDataType* data, int child)
{
			// 找到child的双亲
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (data[child] < data[parent])
		{
			// 如果孩子小于双亲就进行交换
			Swap(&data[child], &data[parent]);
			// 关系转换
			child = parent;
			// 需要继续向上调整
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

 二叉堆显示堆顶元素

HeapDataType HPTop(HP* php)
{

	assert(php);
	return php->data[0];
}

 二叉堆的删除

 顺序表的基本结构

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	// 堆顶元素与末尾元素进行交换，删除最后一个位置
	Swap(&php->data[0], &php->data[php->size-1]);
	php->size--;
	// 针对堆顶位置，做向下调整
	AdjustDown(php->data, php->size, 0);
}

如何 删除 堆顶端的元素，同时维护堆的性质?


实际的操作是将堆顶元素对堆中最后一个元素交换，堆的元素个数-1，然后再从根结点开始进行一次从上向下的调整。调整时先在左右孩子结点中找最小的，如果双亲结点比这个最小的子结点还小说明不需要调整了，反之将双亲结点和它交换后再考虑后面的结点。

下调算法

确定目标子节点： 

parent 从根节点开始，假设目标子节点为左孩子 child = parent*2+1 ，当左孩子在数组范围之内时进入循环

如果 child + 1 (即右孩子)没超过范围 且 data[child+1] < data[child]，则说明右孩子为目标子节点，更新目标子节点 child = child + 1

更新目标亲子关系：

此时 child 为目标子节点，然后再与 parent 双亲结点比较判断是否交换

void AdjustDown(HeapDataType* data, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
			// 兄弟比较，取小为child
		if (child + 1 < n && data[child+1] < data[child])
		{
			child++;
		}
		if (data[child] < data[parent])
		{
			// 父子比较，判断是否交换
			Swap(&data[child], &data[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
<1>将堆顶元素对堆中最后一个元素交换
<2>将堆中有效数据个数减少一个
<3>对堆顶元素进行向下调整

 二叉堆的判空

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

整体代码实现

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

typedef int HeapDataType;

typedef struct Heap
{
	int size;
	int capacity;
	HeapDataType* data;
}HP;

void HPInit(HP* php)
{
	assert(php);
	php->data = NULL;
	php->capacity = php->size = 0;
}

void HPDestroy(HP* php)
{
	assert(php);
	free(php->data);
	php->data = NULL;
	php->capacity = 0;
	php->size = 0;
}

void Swap(HeapDataType* n, HeapDataType* m)
{
	HeapDataType tmp = *n;
	*n = *m;
	*m = tmp;  
}

void AdjustUp(HeapDataType* data, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (data[child] < data[parent])
		{
			Swap(&data[child], &data[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* newNode = (HeapDataType*)realloc(php->data, sizeof(HeapDataType) * newcapacity);
		if (newNode == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		php->data = newNode;   
		php->capacity = newcapacity;
	}
	php->data[php->size] = x;
	php->size++;
	AdjustUp(php->data, php->size - 1);
}

HeapDataType HPTop(HP* php)
{

	assert(php);
	return php->data[0];
}

void AdjustDown(HeapDataType* data, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && data[child+1] < data[child])
		{
			child++;
		}
		if (data[child] < data[parent])
		{
			Swap(&data[child], &data[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->data[0], &php->data[php->size-1]);
	php->size--;
	AdjustDown(php->data, php->size, 0);
}

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



int main()
{
	int a[] = { 60,70,65,50,32,100 };

	HP hp;
	HPInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

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

	HPDestroy(&hp); 

	return 0;
}

代码测试

二叉堆性能：堆是为了实现排序而实现的一种数据结构，它并不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)

不过在 插入 或 删除 某个值 和求二叉树中最值 往往具有很强的高效性

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

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

相关文章

CUDA安装及环境配置——最新详细版

CUDA安装及环境配置——最新详细版

确定安装版本 在安装之前呢&#xff0c;我们需要确定三件事 第一&#xff1a;查看显卡支持的最高CUDA的版本&#xff0c;以便下载对应的CUDA安装包 第二&#xff1a;查看对应CUDA对应的VS版本&#xff0c;以便下载并安装对应的VS版本&#xff08;vs需要先安装&#xff09; 第三…
阅读更多...
基于Jupyter快速入门Python,Numpy,Scipy,Matplotlib

基于Jupyter快速入门Python,Numpy,Scipy,Matplotlib

文章目录 Jupyter 和 Colab 笔记本PythonPython 版本基础数据类型数字Numbers布尔值Booleans字符串Strings 容器列表List字典Dictionaries集合Sets元组Tuples 函数类 Numpy数组Array数组索引Array indexing数据类型DatatypesArray math广播Broadcasting Scipy图像操作MATLAB文件…
阅读更多...
IOS覆盖率报告info文件解读

IOS覆盖率报告info文件解读

一&#xff0c;IOS覆盖率报告的生成 在做前端精准测试的时候&#xff0c;对于iOS端&#xff0c;通常会做如下操作&#xff1a; &#xff08;1&#xff09;合并覆盖率数据 如下操作&#xff1a; xcrun llvm-profdata merge coverage_file1657885040728.profraw coverage_fil…
阅读更多...
Java 可变长参数

Java 可变长参数

可变长参数定义 从 Java5 开始&#xff0c;Java 支持定义可变长参数&#xff0c;所谓可变长参数就是允许在调用方法时传入不定长度的参数。可变长参数允许方法接受任意多个相同类型的参数&#xff0c;在方法内部可以将这些参数视为数组来处理。可变长参数通过省略号&#xff0…
阅读更多...
【洛谷 P8668】[蓝桥杯 2018 省 B] 螺旋折线 题解（数学+平面几何）

【洛谷 P8668】[蓝桥杯 2018 省 B] 螺旋折线 题解（数学+平面几何）

[蓝桥杯 2018 省 B] 螺旋折线 题目描述 如图所示的螺旋折线经过平面上所有整点恰好一次。 对于整点 ( X , Y ) (X, Y) (X,Y)&#xff0c;我们定义它到原点的距离 dis ( X , Y ) \text{dis}(X, Y) dis(X,Y) 是从原点到 ( X , Y ) (X, Y) (X,Y) 的螺旋折线段的长度。 例如 …
阅读更多...
java SSM汽车租赁管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

java SSM汽车租赁管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM汽车租赁管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用…
阅读更多...
【Docker】了解Docker Desktop桌面应用程序，TA是如何管理和运行Docker容器（3)

【Docker】了解Docker Desktop桌面应用程序，TA是如何管理和运行Docker容器（3)

欢迎来到《小5讲堂》&#xff0c;大家好&#xff0c;我是全栈小5。 这是《Docker容器》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对…
阅读更多...
MySQL实战：SQL优化及问题排查

MySQL实战：SQL优化及问题排查

有更合适的索引不走&#xff0c;怎么办&#xff1f; MySQL在选取索引时&#xff0c;会参考索引的基数&#xff0c;基数是MySQL估算的&#xff0c;反映这个字段有多少种取值&#xff0c;估算的策略为选取几个页算出取值的平均值&#xff0c;再乘以页数&#xff0c;即为基数 查…
阅读更多...
Springboot+vue的项目申报管理系统（有报告）。Javaee项目，springboot vue前后端分离项目。

Springboot+vue的项目申报管理系统（有报告）。Javaee项目，springboot vue前后端分离项目。

演示视频&#xff1a; Springbootvue的项目申报管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09…
阅读更多...
盲盒抽卡机小程序——开启神秘之旅！

盲盒抽卡机小程序——开启神秘之旅！

亲爱的朋友们&#xff0c;欢迎来到盲盒抽卡机小程序&#xff01;这里&#xff0c;是一个充满神秘与惊喜的世界&#xff0c;让你随时随地体验抽卡的乐趣。在这里&#xff0c;你可以轻松尝试各种盲盒&#xff0c;发现隐藏的宝藏&#xff0c;感受心跳加速的刺激。 【丰富多样的盲…
阅读更多...
ARM单片机中程序在ROM空间和RAM空间的分布（分散加载文件，Scatter-Loading Description File）

ARM单片机中程序在ROM空间和RAM空间的分布（分散加载文件，Scatter-Loading Description File）

对于 K e i l u V i s i o n I D E Keil\quad uVision\quad IDE KeiluVisionIDE&#xff0c;程序编译好之后&#xff0c;代码的下载位置&#xff08; R O M ROM ROM空间&#xff09;以及代码运行的时候使用的 R A M RAM RAM空间&#xff08; R A M RAM RAM空间&#xff09;默认…
阅读更多...
华为云云耀云服务器L实例评测｜用PHP从数据库到后端到前端完整实现一个中秋节祝福语项目

华为云云耀云服务器L实例评测｜用PHP从数据库到后端到前端完整实现一个中秋节祝福语项目

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年6月CSDN上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师…
阅读更多...
考虑到通信链路中断的(Delay Tolerant Network, DTN)

考虑到通信链路中断的(Delay Tolerant Network, DTN)

文章目录 A Study of DTN for Reliable Data Delivery from Space Station to Ground Stationabstractintroduction An Analytical Framework for Disruption of Licklider Transmission Protocol in Mars Communicationsabstract本文贡献 OVERVIEW OF RELIABLE DATA TRANSMISS…
阅读更多...
Excel转pdf

Excel转pdf

1、excel-内存值--Workbook 转pdf /** * excel To pdf * * param outPath 输出路径 * param workbook excel-内存值 * throws IOException */ public static void excelToPdf(String outPath,Workbook workbook) throws IOException, DocumentException { Document documentnul…
阅读更多...
Android studio Gradle下载失败，如何手动配置解决该问题详解

Android studio Gradle下载失败，如何手动配置解决该问题详解

前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下"通俗易懂&#xff0c;风趣幽默"&#xff0c;感觉非常有意思,忍不住分享一下给大家。 &#x1f449;点击跳转到教程 前言&#xff1a; 今天在打开公司一个项目时&#xff0c;突然要重新下载相关的gradle&am…
阅读更多...
图机器学习（4）-面向连接层面的人工特征工程

图机器学习（4）-面向连接层面的人工特征工程

0 问题定义 通过已经连接去猜未知连接&#xff1a; 有两个思路&#xff1a; &#xff08;1&#xff09;直接提取link的特征&#xff0c;把link变成D维向量&#xff1b; &#xff08;2&#xff09;把link两端节点的D维向量拼在一起&#xff0c;缺点&#xff1a;丢失了link本身…
阅读更多...
CSAPP-程序的机器级表示

CSAPP-程序的机器级表示

文章目录 概念扫盲思想理解经典好图安全事件 概念扫盲 1.汇编代码使用文本格式&#xff0c;相较于汇编的二进制可读性更好 2.程序内存包括&#xff1a;可执行的机器代码、操作系统需要的信息、管理过程调用和返回的运行时栈、用户分配的内存块 3.链接器为函数调用找到匹配的可…
阅读更多...
基于SpringBoot宠物领养系统的设计与实现(代码+数据库+文档)

基于SpringBoot宠物领养系统的设计与实现(代码+数据库+文档)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…
阅读更多...
运维：记一次寻找定时任务并删除的经历

运维：记一次寻找定时任务并删除的经历

前言 我相信接手别人的服务器、或者在没有任何文档的情况去看自己原先的服务器，都或多或少会遇到莫名其妙的服务器独有规则。 比如你服务本身跑的好好的，突然啪的一下，没了！ 什么原因导致的呢？其中，很大可能是定时任务在作祟。 原因分析 本次，我遇到的问题是：在Ubuntu系…
阅读更多...
基于GitBucket的Hook构建ES检索PDF等文档全栈方案

基于GitBucket的Hook构建ES检索PDF等文档全栈方案

背景 之前已简单使用ES及Kibana和在线转Base64工具实现了检索文档的demo&#xff0c;预期建设方案是使用触发器类型从公共的文档源拉取最新的文件&#xff0c;然后调用Java将文件转Base64后入ES建索引&#xff0c;再提供封装接口给前端做查询之用。 由于全部内容过长&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023