当前位置: 首页 > news >正文

【数据结构】堆的向上调整和向下调整以及相关方法

在这里插入图片描述

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃

文章目录

  • 一、堆的概念
  • 二、堆的性质
  • 三、堆的分类
    • 1.大根堆
    • 2.小根堆
  • 四、说明
  • 五、堆的结构
  • 🚩六、堆的向上调整
    • 1.图示
    • 2.代码实现
    • ⌚️3.时间复杂度分析
  • 📌七、堆的向下调整
    • 1.思路:
    • 2.代码实现
    • ⌚️3.时间复杂度分析
  • 八、删除根
    • 1.思路:
    • 2.代码实现
    • ⌚️3.时间复杂度分析
  • 九、创建堆
    • 1.思路:
    • 2.代码实现
  • 十、所有方法实现汇总

一、堆的概念

堆(Heap)是计算机科学中一类特殊的数据结构的统称。如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。除了最后一层以外上面的节点但是非空的,最后一层节点是从左到右依次排布的)

二、堆的性质

🔸 非线性,完全二叉树。适合用数组存储。
🔸堆是无序的,也就是左右可以互换
🔸最值总在 0 号位
根据这个特点我们就可以做很多事情,比如TopK问题 (在一堆数据里面找到前 K 个最大 / 最小的数).
比如点餐软件中有上千家店铺,我想选出该地区好评最多的十家川菜店,我们不用对所有数据排序,只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。

三、堆的分类

1.大根堆 2.小根堆

1.大根堆

定义:树中的任意一个双亲节点都大于等于孩子节点。
在这里插入图片描述

2.小根堆

定义:树中的任意一个双亲节点都小于等于孩子节点。

在这里插入图片描述

四、说明

以下的方法均以小堆来推理,如果想实现大堆,则修改【<】符号等方式实现。

五、堆的结构

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

🚩六、堆的向上调整

向上调整的前提是,调整位置之前必须是堆。如果目的是调成小堆,则要保证调整位置之前是小堆;如果目的是调成大堆,则要保证调整位置之前是大堆。

1.图示

在这里插入图片描述

2.代码实现

//向上调整
void AdjustUp(HPDataType* a, int child)
{//传入数组,child为孩子节点下标int parent = (child - 1) / 2;//当一直交换到根,停止while (child>0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}elsereturn;}
}

⌚️3.时间复杂度分析

时间复杂度:O(logN)
最坏情况:调整到根;
最好情况:不用调整,

📌七、堆的向下调整

向下调整的前提是,左右子树必须是小堆或者大堆。

1.思路:

如图:
此案例是要调整根节点40开始向下调整,首先确保根节点的左右子树是小堆(由图得成立)。
1.parent的两个孩子进行比较,选出小的。
2.进行交换
3.child>n结束
在这里插入图片描述

2.代码实现

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//一直交换到数的最后,也就是数组的最后一个位置while (parent<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{return;}}
}

⌚️3.时间复杂度分析

时间复杂度:O(logN)
最坏情况:调整到根;
最好情况:不用调整,

八、删除根

1.思路:

1.先将根与最后一个节点交换,
2.删除最后一个节点;
3.进行向下调整。

在这里插入图片描述

2.代码实现

void HeapPop(HP* p)
{assert(p);assert(p->size > 0);Swap(&p->a[0], &p->a[p->size - 1]);--p->size;AdjustDown(p->a, p->size, 0);
}

⌚️3.时间复杂度分析

时间复杂度:O:N(logN)

九、创建堆

创建堆的思路可以通过向上调整,也可通过向下调整。这里讲通过向上调整建立堆。
由于我的AdjustUp函数是用来调整小堆的,所以,这里创建的也是小堆。

1.思路:

传入参数
a:数组,n:是数组元素个数
1.为p->a开辟n个空间;
2.利用memcpy函数,把数组a复制到p->a中
3.在使用AdjustUp调整,从1-n-1逐步向下延伸;
在这里插入图片描述
在这里插入图片描述

2.代码实现

//建立小堆
void HeapInitArray(HP* p, int* a, int n)
{//a:数组,n:是数组元素个数assert(p);assert(a);p->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (p->a == NULL){perror("malloc fail");exit(-1);}p->size = n;p->capacity = n;//把传入数组a复制到p->a中memcpy(p->a, a, sizeof(HPDataType) * n);// 向上调整,调整成一个小堆for (int i = 1; i < n; i++){AdjustUp(p->a, i);}
}

十、所有方法实现汇总

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//初始化
void HeapInit(HP* p)
{assert(p);p->a = NULL;p->size = 0;p->capacity = 0;
}//销毁
void HeapDestroy(HP* p)
{assert(p);free(p->a);p->a = NULL;p->size = p->capacity = 0;
}//插入数据
void HeapPush(HP* p, HPDataType x)
{//从最后一个位置插入assert(p);//扩容if (p->capacity == p->size){//如果刚开始数组为空,就开辟4个空间。如果不为空,以后每次扩大2倍。int newcapacity = p->capacity==0 ? 4 : p->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * p->capacity);if (tmp == NULL){perror("realloc fial\n");exit(-1);}p->a = tmp;p->capacity = newcapacity;}p->a[p->size] = x;p->size++;AdjustUp(p->a, p->size-1);
}//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上调整
void AdjustUp(HPDataType* a, int child)
{//传入数组,child为孩子节点下标int parent = (child - 1) / 2;//当一直交换到根,停止while (child>0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}elsereturn;}
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//一直交换到数的最后,也就是数组的最后一个位置while (parent<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{return;}}
}//打印二叉树
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}//建立小堆
void HeapInitArray(HP* p, int* a, int n)
{//a:数组,n:是数组元素个数assert(p);assert(a);p->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (p->a == NULL){perror("malloc fail");exit(-1);}p->size = n;p->capacity = n;//把传入数组a复制到p->a中memcpy(p->a, a, sizeof(HPDataType) * n);// 向上调整,调整成一个小堆for (int i = 1; i < n; i++){AdjustUp(p->a, i);}
}//删除根
void HeapPop(HP* p)
{assert(p);assert(p->size > 0);Swap(&p->a[0], &p->a[p->size - 1]);--p->size;AdjustDown(p->a, p->size, 0);
}
//获取根
HPDataType HeapTop(HP* p)
{assert(p);assert(p->size > 0);return p->a[0];
}//判空
bool HeapEmpty(HP* p)
{assert(p);return p->size == 0;
}

相关文章:

【数据结构】堆的向上调整和向下调整以及相关方法

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3; 文章目录 一、堆的概念二、堆的性质…...

【蓝桥杯选拔赛真题60】Scratch旋转风车 少儿编程scratch图形化编程 蓝桥杯选拔赛真题解析

目录 scratch旋转风车 一、题目要求 编程实现 二、案例分析 1、角色分析...

JavaSE、JavaEE与Spring的概念和异同点剖析以及规范13 个分析

JavaSE、JavaEE与Spring的概念和异同点剖析以及规范13 个分析 目录概述需求&#xff1a; 设计思路实现思路分析1.什么是JavaSE2.是JavaEE3.什么是Spring 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,full busy&…...

微信小程序的图书馆图书借阅 座位预约系统 读者端设计与实现

该系统基于B/S即所谓浏览器/服务器模式&#xff0c;应用springboot框架&#xff0c;选择MySQL作为后台数据库。系统主要包括系统图书信息、图书借阅、图书归还、自习室信息、自习室预约等功能模块。 关键词 微信小程序的图书馆读者端&#xff1b;微信小程序&#xff1b;java语…...

在阿里云 linux 服务器上查看当前服务器的Nginx配置信息

我们可以通过命令 sudo nginx -t查看到nginx.conf的路径 可以通过 sudo nginx -T查看 nginx 详细配置信息&#xff0c;包括加载的配置文件和配置块的内容 其中也会包括配置文件的内容...

专业招投标书翻译怎样做比较好

在全球经济贸易一体化不断深入的时代&#xff0c;招投标作为国际通用的新型贸易方式&#xff0c;受到了大量中外企业的青睐。根据国际惯例&#xff0c;与招标采购活动有关的一切文件资料&#xff0c;均须使用英文编制。即使允许使用非英文语言编制&#xff0c;也必须随附一份英…...

算法总结10 线段树

算法总结10 线段树 线段树2569. 更新数组后处理求和查询 线段树 有一个数组&#xff0c;我们要&#xff1a; 更新数组的值&#xff08;例如&#xff1a;都加上一个数&#xff0c;把子数组内的元素取反&#xff09;查询一个子数组的值&#xff08;例如&#xff1a;求和&#x…...

518抽奖软件,支持按人像照片抽奖

518抽奖软件简介 518抽奖软件&#xff0c;518我要发&#xff0c;超好用的年会抽奖软件&#xff0c;简约设计风格。 包含文字号码抽奖、照片抽奖两种模式&#xff0c;支持姓名抽奖、号码抽奖、数字抽奖、照片抽奖。(www.518cj.net) 照片抽奖模式 圆角边框 照片抽奖模式下&am…...

数字IC笔试面试题之--时钟偏斜(skew)与抖动(jitter)

1 时钟偏斜&#xff08;clock skew&#xff09; 时钟偏斜&#xff08;偏移&#xff09;是因为布线长度和负载不同&#xff0c;导致同一时钟上升沿到不同触发器的时间不同。这一时间差&#xff0c;即为时钟偏移。 时钟偏斜可能导致时序违例&#xff08;本文直接粘贴了参考博客…...

免费api接口:物流api,企业工商查询api,游戏api。。。

免费api接口&#xff0c;物流api,企业工商查询api,游戏api。。。都有。 Facebook Games Services - Facebook Games Services 为游戏开发者提供了各种服务, 包括(但不限于) 成就 API, 分数 API, 应用通知, 请求, 游戏养成和 Facebook SDK for Unity.Google Play Games Service…...

第二十八章 Classes - 引用其他类的方法

文章目录 第二十八章 Classes - 引用其他类的方法引用其他类的方法对当前实例的引用 第二十八章 Classes - 引用其他类的方法 引用其他类的方法 在方法(或例程)中&#xff0c;使用下面的语法来引用其他类中的方法: 要调用类方法并访问其返回值&#xff0c;请使用如下表达式:…...

Android 中集成 TensorFlow Lite图片识别

在上图通过手机的相机拍摄到的物体识别出具体的名称&#xff0c;这个需要通过TensorFlow 训练的模型引用到项目中&#xff1b;以下就是详细地集成 TensorFlow步骤&#xff0c;请按照以下步骤进行操作&#xff1a; 在项目的根目录下的 build.gradle 文件中添加 TensorFlow 的 Ma…...

NSSCTF之Misc篇刷题记录(16)

NSSCTF之Misc篇刷题记录&#xff08;16&#xff09; [黑盾杯 2020]encrypt[UTCTF 2020]Spectre[UTCTF 2020]Observe closely NSSCTF平台&#xff1a;https://www.nssctf.cn/ PS&#xff1a;所有FLAG改为NSSCTF [黑盾杯 2020]encrypt UTAxSlUwTkRWRVo3Um1GclpWOWxibU55ZVhCMGFX…...

域名解析--nslookup和dig

dig (Domain Information Groper) dig 是一个功能强大且更灵活的 DNS 查询工具&#xff0c;通常在 Linux 和 macOS 等 Unix-like 操作系统上使用。以下是 dig 的一些常见用法和区别&#xff1a; 查询域名信息 dig example.com这将返回与指定域名相关的 DNS 记录&#xff0c;…...

EXCEL如何把一个单元格内的文本和数字分开?例如:龚龚15565 = 龚龚 15565

使用工具&#xff1a;WPS 举例&#xff1a; EXCEL如何把一个单元格内的文本和数字批量分开&#xff1f;不使用数据分列。 第一步、将第二行数据冻结 第二步、在B1、C1单元格输入需要分开的示例 第三步、点击选中B1单元格&#xff0c;输入快捷键【CTRLE】进行填充。B2单元格也是…...

uniapp抽取组件绑定事件中箭头函数含花括号无法解析

版本: "dcloudio/uni-ui": "^1.4.27", "vue": "> 2.6.14 < 2.7"... 箭头函数后含有花括号的时候, getData就拿不到val参数 , 解决办法就是去除花括号 // 错误代码: <SearchComp change"(val) > { getData({ val …...

猫头虎博主第四期赠书活动:《精通Go语言:(第2版) 》

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

【学习总结】EasyExcel合并同列不同行,表格数据相同的行

实体类 Data HeadRowHeight(50) ContentStyle(horizontalAlignment HorizontalAlignmentEnum.CENTER, verticalAlignment VerticalAlignmentEnum.CENTER, wrapped BooleanEnum.TRUE) public class CriterionDataExportDTO {ColumnWidth(15)ExcelProperty(value "所属…...

Tokenview X-ray功能:深入探索EVM系列浏览器的全新视角

Tokenview作为一家领先的多链区块浏览器&#xff0c;为了进一步优化区块链用户的使用体验&#xff0c;我们推出了X-ray&#xff08;余额透视&#xff09;功能。该功能将帮助您深入了解EVM系列浏览器上每个地址的交易过程&#xff0c;以一种直观、简洁的方式呈现地址的进出账情况…...

【洛谷 P1364】医院设置 题解(图论+深度优先搜索)

医院设置 题目描述 设有一棵二叉树&#xff0c;如图&#xff1a; 其中&#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号&#xff0c;现在要求在某个结点上建立一个医院&#xff0c;使所有居民所走的路程之和为最小&#xff0c;同时约定&#xff0c;相邻接…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...