数据结构之堆

目录

前言

堆的概念与结构

堆的实现

 堆的初始化

堆的销毁

堆的显示

堆的插入

堆的向上调整算法

堆的删除

堆的向下调整算法

堆的判空

获取堆顶元素

 堆的数据个数

堆的创建


前言

二叉树的顺序结构存储即使用数组存储,而数组存储适用于完全二叉树完全二叉树不会存在空间上的浪费二叉树的顺序存储在物理上是一个数组,在逻辑上是一颗二叉树

完全二叉树的顺序存储可以根据下标寻找孩子结点或者父结点,规律如下

leftchild=2*parent+1,   rightchild=2*parent+2;

parent=(child-1)/2 ;

堆的概念与结构

堆的定义:

如果有一个关键码的集合K = {K1 ,K2 ,K3 ,…,Kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki <=K2i+1且Ki<=K2i+2(Ki >= K2i+1且Ki >= K2i+2) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆;
堆的性质:
  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树
  • 小根堆示意图

  • 大根堆示意图

堆的实现

 堆总是一棵完全二叉树,堆是用数组存储的;

//堆结构的定义
//由于是顺序存储,采用顺序表定义
typedef int HeapDataType;
typedef struct Heap
{HeapDataType* nums;//数组int size;//数据个数int capacity;//记录数组容量
}Heap;

 堆的初始化

//堆的初始化
void HeapInit(Heap* php)
{assert(php != NULL);php->nums = (HeapDataType*)malloc(sizeof(HeapDataType)*4);if (php->nums == NULL){perror("malloc failed:");exit(-1);}php->size = 0;php->capacity = 4;
}

堆的销毁

void HeapDestroy(Heap* php)
{assert(php != NULL);free(php->nums);php->nums = NULL;php->size = 0;php->capacity = 0;
}

堆的显示

//堆的显示
void HeapPrint(Heap* php)
{assert(php != NULL);for (int i = 0; i < php->size; i++){printf("%d ", php->nums[i]);}printf("\n");
}

堆的插入

堆的插入是在堆尾的下一个位置插入数据并保证数组的逻辑结构为堆;

  • case 1:

当在数组尾元素的下一个位置插入的数据其值大于等于父节点的值时,仍然为小堆;

  • case 2:

当在数组尾元素的下一个位置插入的数据其值小于父节点的值时,堆的逻辑结构被破坏,采用向上调整算法,将其调整为堆;

堆的向上调整算法

由于堆的逻辑结构为小堆,孩子结点处插入的数值小于其父节点处的值,堆的逻辑结构被破坏;首先交换child位置处与parent位置处的值,然后child=parent,parent=(child-1)/2,继续比较孩子节点与父亲结点处的数值,若不满足小堆,继续向上调整,直至根结点的位置为止或出现满足小堆的数值出现停止;

case 1:

case 2:

向上调整算法的时间复杂度

当插入的数据不需要调整,时间复杂度为O(1);

当插入的数据一直调整到根结点处,调整了高度h次,设满二叉树的结点个数为N,则h=log2(N+1),那么其时间复杂度为O(logn);

综上所述,时间复杂度为O(logn);

//交换
void swap(HeapDataType* p1, HeapDataType* p2)
{HeapDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//堆的向上调整算法
void AdjustUp(HeapDataType* nums, int child)
{int parent = (child - 1) / 2;while (child>0){if (nums[child] < nums[parent]){swap(&nums[child], &nums[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}
//堆的插入
void HeapPush(Heap* php, HeapDataType x)
{assert(php != NULL);//检查数组容量,容量满时扩容;if (php->size == php->capacity){HeapDataType* tmp = (HeapDataType*)realloc(php->nums, sizeof(HeapDataType)* 2 * (php->capacity));if (tmp == NULL){perror("realloc failed:");exit(-1);}php->nums = tmp;php->capacity = 2 * (php->capacity);}//插入堆的叶结点即二叉树的叶节点php->nums[php->size] = x;php->size++;//任意数据插入之后还是堆吗?//结论是否定的-->向上调整算法-->调整为堆//参数设计为指向数组首元素的指针与数组尾元素的下标,返回值为空AdjustUp(php->nums, php->size - 1);
}

堆的删除

堆的删除是删除堆顶数据,并且保证其逻辑结构仍然为堆,删除的方法是将堆顶的数据与最后一个数据交换,然后删除数组最后一个数据,最后进行向下调整算法,保证其逻辑结构为堆;

堆的向下调整算法

首先利用假设法寻找同一高度处值最小的孩子,根据其左右子树为小堆还是大堆,按照小堆或大堆的原则将其交换,若为小堆,父节点处的数值大于孩子结点出的数值,则交换彼此位置;若为大堆,父节点处的数值小于孩子结点出的数值,则交换彼此位置;直至叶节点为止或出现满足其逻辑上大小堆的数值为止;

堆向下调整算法的时间复杂度为O(logN);

//堆的向下调整算法
void AdjustDown(HeapDataType* nums, int n, int parent)
{//假设法求同一深度左右孩子最小的一个,假设左孩子为最小int child = parent * 2 + 1;while (child<n){if (child+1 < n && nums[child] > nums[child + 1]){child++;}//无论左右孩子,child为最小,调整为小堆;if (nums[child] < nums[parent]){swap(&nums[child], &nums[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}
//堆的删除
void HeapPop(Heap* php)
{//删除数组首元素,并且保证逻辑为堆;assert(php != NULL);assert(php->size > 0);swap(&php->nums[0],&php->nums[php->size - 1]);php->size--;//向下调整AdjustDown(php->nums, php->size, 0);
}

堆的判空

//堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

获取堆顶元素

//取堆顶元素
HeapDataType HeapTop(Heap* php)
{assert(php != NULL);assert(php->size > 0);return php->nums[0];
}

堆的数据个数

//堆的数据个数
int HeapSize(Heap* php)
{assert(php != NULL);return php->size;
}

堆的创建

给定一个数组,这个数组逻辑上是一颗完全二叉树,而且不一定为堆,通过向上调整算法将其构建为堆;建堆的思想为以数组首元素的下一个位置为起点,利用向上调整算法,依次插入元素建堆;

void HeapCreate(Heap* php, HeapDataType* nums, int n)
{assert(php != NULL);php->nums = (HeapDataType*)malloc(sizeof(HeapDataType)*n);if (php->nums == NULL){perror("malloc fail:");exit(-1);}php->size = php->capacity = n;memcpy(php->nums, nums, sizeof(HeapDataType)*n);//建堆,建堆的时间复杂度为O(N*logN);for (int i = 1; i < n; i++){AdjustUp(php->nums, i);}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C# OpenVINO Cls 图像分类

效果 耗时 class idbrown_bear, score0.86 preprocess time: 0.00ms infer time: 2.72ms postprocess time: 0.02ms Total time: 2.74ms项目 代码 using OpenCvSharp; using Sdcb.OpenVINO; using Sdcb.OpenVINO.Natives; using System; using System.Diagnostics; using Sys…

【分享】教你加速访问GitHub,进来学!

哈喽&#xff0c;大家好&#xff0c;木易巷来啦&#xff01; 众所周知&#xff0c;Github是一款程序猿必备的代码托管平台&#xff0c;上面已经存在了无数前辈的心血&#xff01;经常需要在上面查看大佬写的一些好用的开源项目&#xff0c;无赖国外网站的速度实在让人难以接受。…

基于ssm+vue的线上点餐系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

间歇性微服务问题...

在Kubernetes环境中&#xff0c;最近由于特定配置导致Pod调度失败。哪种 Kubernetes 资源类型&#xff08;通常与节点约束相关&#xff09;可能导致此故障&#xff0c;尤其是在未正确定义的情况下&#xff1f; 节点选择器资源配额优先级污点Pod 中断预算 已有 201 人回答了该…

华为数通方向HCIP-DataCom H12-831题库(单选题:261-280)

第261题 某网络通过部署1S-IS实现全网与通,若在一台IS-IS路由器的某接口下配置命令isis timer holding multiplier 5 level-2,则以下关于该场景的描述,正确的是哪一项? A、该接口Level-2邻居保持时间为5秒 B、该接口Level-1邻居保持时间为30秒 C、该接口为点对点链路接口 …

工控网络协议模糊测试:用peach对modbus协议进行模糊测试

0x00 背景 本人第一次在FB发帖&#xff0c;进入工控安全行业时间不算很长&#xff0c;可能对模糊测试见解出现偏差&#xff0c;请见谅。 在接触工控安全这一段时间内&#xff0c;对于挖掘工控设备的漏洞&#xff0c;必须对工控各种协议有一定的了解&#xff0c;然后对工控协议…

Qt开发之路--模块化设计.pri文件

Qt开发之路--模块化设计.pri文件 QT pro文件和pri文件的区别Chapter1 Qt开发之路--模块化设计.pri文件一&#xff1a;.pri文件简介二&#xff1a;通过.pri模块化设计三&#xff1a;结尾 Chapter2 Qt开发大型项目时&#xff0c;通过.pri文件将众多文件按功能模块分类显示Qt中多p…

概率神经网络分类问题程序

欢迎关注“电击小子程高兴的MATLAB小屋” %% 概率神经网络 %% 解决分类问题 clear all; close all; P[1:8]; Tc[2 3 1 2 3 2 1 1]; Tind2vec(Tc) %数据类型的转换 netnewpnn(P,T); Ysim(net,P); Ycvec2ind(Y) %转换回来

7天狂揽 1.3w star 的 MetaGPT,他们的目标让软件公司为之一惊

在 AI 产品爆炸的今天&#xff0c;拥有各种本领的 AI 产品层出不穷&#xff0c;但 MetaGPT 的出现仍然显的格外耀眼&#xff0c;其可以实现只输入单一 prompt&#xff0c;就可以输出需求分析、需求文档、技术架构、最终代码等等产物&#xff0c;这相当于一个开发团队的输出成果…

Linux:【Kafka四】集群介绍与单机搭建

目录 环境简介 一、搭建kafka集群 1.1、复制出两个kafka的配置文件 1.2、修改配置文件中的如下属性 二、启动kafka集群 三、可校验kafka三个节点是否均启动成功 四、查看集群中主题的分区和副本 4.1、新建一个包含了分区和副本的主题 4.2、查看该主题的详细信息 五、…

Android查看签名信息系列 · 使用逆向分析工具JadxGUI获取签名

前言 Android查看签名信息系列之使用逆向分析工具JadxGUI获取签名&#xff0c;通过这种方式&#xff0c;可以获取到的签名信息包括&#xff1a;MD5、SHA1、SHA-256、公钥(模数)等信息 实现方法 1、进入JadxGUI目录下的lib文件夹内&#xff0c;找到jadx-gui-1.4.7.jar文件 2、…

计算机网络第2章-HTTP和Web协议(2)

Web和HTTP 一个新型应用即万维网&#xff08;World Wide Web&#xff09;Web。 HTTP概况 Web的应用层协议是超文本传输协议&#xff08;HTTP&#xff09;&#xff0c;它是Web的核心。 HTTP由两个程序实现&#xff1a;一个用户程序和一个服务器程序。 Web页面&#xff08;W…

VSCode 调试 u-boot

文章目录 VSCode 调试 u-boot调试配置启动 u-boot 脚本调试界面重定向之后继续调试参考 VSCode 调试 u-boot 调试配置 参考 qemu基础篇——VSCode 配置 GDB 调试 要想调试 u-boot 只需要再添加一个 u-boot 的配置即可 {"version": "0.2.0","conf…

如果你有一次自驾游的机会,你会如何准备?

常常想来一次说走就走的自驾游&#xff0c;但是光是想想就觉得麻烦的事情好多&#xff1a;漫长的公路缺少娱乐方式、偏僻拗口的景点地名难以导航、不熟悉的城市和道路容易违章…… 也因为如此&#xff0c;让我发现了HUAWEI HiCar这个驾驶人的宝藏&#xff01; 用HUAWEI HiCar…

科研上新 | 第2期:可驱动3D肖像生成;阅读文本密集图像的大模型;文本控制音色;基于大模型的推荐智能体

编者按&#xff1a;欢迎阅读“科研上新”栏目&#xff01;“科研上新”汇聚了微软亚洲研究院最新的创新成果与科研动态。在这里&#xff0c;你可以快速浏览研究院的亮点资讯&#xff0c;保持对前沿领域的敏锐嗅觉&#xff0c;同时也能找到先进实用的开源工具。 本期内容速览 …

16 个 Linux 最佳 Markdown 编辑器(2)

对于初学者来说&#xff0c;Markdown 是一个用 Perl 编写的简单且轻量级的工具&#xff0c;它使用户能够编写纯文本格式并将其转换为有效的 HTML&#xff08;或 XHTML&#xff09;。它是一种易于阅读、易于编写的纯文本语言&#xff0c;也是一种用于文本到 HTML 转换的软件工具…

操作系统四大特征

OS四大特征 1.OS的并发性&#xff08;同一时间间隔内执行和调度多个程序的能力&#xff09; 宏观上&#xff0c;处理机同时执行多道程序 微观上&#xff0c;处理机在多道程序间高速切换(分时交替执行)&#xff0c;微观上并非是同时执行的。 关注单个处理机同一时间段内处理任…

IOS课程笔记[4-5] 计算器实现与更换主题 的使用

计算 控件介绍 文本输入 设置键盘格式为NumberPad字符串与数字转换方法 NSInteger num2 [str2 integerValue]; 弹窗控件 UIAlertController 新版本弹窗 UIAlertController *alert [UIAlertController alertControllerWithTitle:"error" message:"输入有…

数据结构-----红黑树的插入

目录 前言 红黑树的储存结构 一、节点旋转操作 左旋&#xff08;Left Rotation&#xff09; 右旋&#xff08;Right Rotation&#xff09; 二、插入节点 1.插入的是空树 2.插入节点的key重新重复 3.插入节点的父节点是黑色 4.插入节点的父节点是红色 4.1父节点是祖父…

软考-网络安全体系与网络安全模型

本文为作者学习文章&#xff0c;按作者习惯写成&#xff0c;如有错误或需要追加内容请留言&#xff08;不喜勿喷&#xff09; 本文为追加文章&#xff0c;后期慢慢追加 by 2023年10月 网络安全体系相关安全模型 BLP机密性模型 BLP&#xff08;Biba-格雷泽-麦克拉伦&#x…