数据结构-堆
1.容器
容器用于容纳元素集合,并对元素集合进行管理和维护.
传统意义上的管理和维护就是:增,删,改,查.
我们分析每种类型容器时,主要分析其增,删,改,查动作实现,及复杂度.
2.堆
2.1.结构
2.1.1.图解
堆是容器类型.
采用容器内元素在线性空间连续存储的组织方式(数组也是如此).
但除此之外,基于元素的组织方式,为其抽象出了一层二叉树的逻辑关系.
以一个具体实例来说明.
上图是代表了一个可容纳12
个元素的线性空间.现在存储了8
个有效元素.堆的元素存储和数组一致.
但堆为其顺序存储的元素抽象出了一层二叉树的逻辑关系.
抽象的过程为,对顺序存储的每个元素,依次用这些元素顺序填满一颗满二叉树.
所谓满二叉树指的是,除了树最后一层,其余各层均是满的.最后一层,最后一个元素左边各个元素均是存在的.
如果观察特点可以得出以下结论,对顺序存储中索引为nIndex
的元素.
逻辑结构里,其左孩子是索引为(2*nIndex+1)
的元素,其右孩子是索引为(2*nIndex+2)
的元素.
堆针对逻辑结构又施加了一层限制.
对最大堆来说,这层限制是:对堆中任一元素,该元素需要大于等于其左孩子,其右孩子上的元素.
对最小堆来说,这层限制是:对堆中任一元素,该元素需小于等于其左孩子,其右孩子上的元素.
在以上条件均满足下,可被利用的性质是:
(1). 首个元素是所有元素中最大的(对最大堆),最小的(对最小堆).
(2). 抽象出来的二叉树由于是满二叉树,其高度为:log
以2
为底n
的对数.
2.1.2.存在一致性约束容器特点
(1). 插入无需提供位置信息.
(2). 不支持直接原地修改.一般分解为移除,添加两个过程.
(3). 由于元素值决定其位置,这类容器一般插入元素时,以std::pair<key, value>
形式插入.即元素包含键,值两部分.键用来实现一致性约束.值是此键关联的实际内容.
2.2.动作
2.2.0.建堆
意思是直接给一个连续存储的元素集合,把这些元素集合调整为符合堆性质的元素集合.
最直观当然是对集合内每个元素直接执行插入,这样所有元素插入完毕,就得到一个由这些元素构成的堆.
这里介绍另一种方式.
从集合最后一个元素反向遍历到第一个元素.
对每次遍历到的元素,让其符合:以该元素为根子树中所有元素均满足堆的性质.
下面介绍针对每个遍历到元素的调节过程.
不妨假设我们现在遍历到的元素是p
.假设是最小堆.
由于我们之前每次遍历时,均按上述要求.所以,p
的左孩子为根子树中所有元素此时均满足堆的性质.p
的右孩子为根子树也是如此.此刻子树中唯一可能不满足要求的就是p
和其左,右孩子.
若p
小于其左,右孩子上的元素,则无需调节.
否则,找到三者中最小元素q
.交换此q
和p
的位置.
交换后对p
和其左右孩子来说堆的性质得到满足.但对q
来说,由于此位置元素变大了.所以,此刻子树中只有q
与其左右孩子可能不满足堆的性质.这样,我们虽然未立即解决问题.但将问题转化为了一个同类型问题.
由于树的高度有限,每次转化后我们在更低一层子树上再次处理同类问题.
故,即使最坏下,至多经过有限次调节,也可解决问题.
2.2.1.增
堆中插入新元素.对于存在一致性约束的容器,元素插入到容器后,需经历调节过程.不需要也无法在指定位置实现插入.具体位置依赖调节过程.
插入过程可描述为:
(1). 将新元素放在数组尾后位置.
(2). 这样,此时数组对应的二叉树中,只有新节点p
和其父亲q
可能不满足堆的性质.
(3). 我们分析最小堆场景.比较p
和q
,若q
中元素小于等于p
,则无需调节.
(4). 若q
中元素大于p
,交换p
,q
内元素.交换后,由于q
位置元素变小了.所以,q
和其父节点可能不满足堆的性质.p
位置元素变小了.故,以p
和其左右孩子必然满足堆的性质.
这样,我们虽然未立即解决问题,但将问题转化了.由于树的高度有限,故,最坏下也能经过有限次迭代结束调节过程.
2.2.2.删
堆由于其性质,一般移除限定只能移除首个元素.我们分析移除首个元素过程.
删除首元素可描述为:
(1). 交换尾元素和首元素.递减有效元素数量.
(2). 我们分析最小堆场景.此时,首元素p
相比原来变大了.此时,整棵树中只有p
和其左右孩子可能不满足堆的性质.
(3). 我们寻找节点p
,其左孩子lp
,其右孩子rp
,三者中最小元素及其位置.
(4). 若最小元素是p
,则无需调节.
(5). 若最小元素是某个孩子cp
(要么lp
,要么rp
).交换cp
和p
上元素.这样,交换后p
和其左右孩子此时满足了堆的性质.但cp
上元素变大了,所以,此时cp
和其左右孩子可能不满足堆的性质.
这样,我们虽然未能立即解决问题.但将问题转化了.由于树的高度有限,故,最环下也能经过有限次迭代结束调节过程.
2.2.3.查
堆一般只提供访问首元素方法即可.
访问首元素直接基于索引访问即可.
2.2.4.改
对于存在一致性约束的容器,一般不会允许直接修改元素的值.
此类操作一般分解为:删除老元素,添加新元素两个过程来实现.
删除非首元素,类似删除首元素过程.只不过此时先交换删除位置元素和尾部元素.再从此开始进入调节流程.
2.3.时间复杂度
评价容器的依据一个是其占据的线性空间,一个是操作执行的时间复杂度.
堆的各个操作时间复杂度为:
(1). 增:Θ(log
以2
为底n
的对数)
(2). 删:Θ(log
以2
为底n
的对数)
(3). 查:Θ(1
) (索引访问)
(4). 改:Θ(1
) (log
以2
为底n
的对数)
相关文章:
数据结构-堆
1.容器 容器用于容纳元素集合,并对元素集合进行管理和维护. 传统意义上的管理和维护就是:增,删,改,查. 我们分析每种类型容器时,主要分析其增,删,改ÿ…...
奔跑吧小恐龙(Java)
前言 Google浏览器内含了一个小彩蛋当没有网络连接时,浏览器会弹出一个小恐龙,当我们点击它时游戏就会开始进行,大家也可以玩一下试试,网址:恐龙快跑 - 霸王龙游戏. (ur1.fun) 今天我们也可以用Java来简单的实现一下这…...
Ubuntu 1804 And Above Coredump Settings
查看 coredump 是否开启 # 查询, 0 未开启, unlimited 开启 xiaoUbuntu:/var/core$ ulimit -c 0# 开启 xiaoUbuntu:/var/core$ ulimit -c unlimited查看 coredump 保存路径 默认情况下,Ubuntu 使用 apport 服务处理 coredump 文件ÿ…...
docker 2:安装
docker 2:安装 ubuntu 安装 docker sudo apt install docker.io 把当前用户放进 docker 用户组,避免每次运行 docker 命都要使用 sudo 或者 root 权限。 sudo usermod -aG docker $USERid $USER 看到用户已加入 docker 组 …...
LeetCode Python - 19.删除链表的倒数第N个结点
目录 题目答案运行结果 题目 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2: 输入:head [1], n 1 输出&a…...
Spring Boot 笔记 005 环境搭建
1.1 创建数据库和表(略) 2.1 创建Maven工程 2.2 补齐resource文件夹和application.yml文件 2.3 porn.xml中引入web,mybatis,mysql等依赖 2.3.1 引入springboot parent 2.3.2 删除junit 依赖--不能删,删了会报错 2.3.3 引入spring web依赖…...
【解决(几乎)任何机器学习问题】:超参数优化篇(超详细)
这篇文章相当长,您可以添加至收藏夹,以便在后续有空时候悠闲地阅读。 有了优秀的模型,就有了优化超参数以获得最佳得分模型的难题。那么,什么是超参数优化呢?假设您的机器学习项⽬有⼀个简单的流程。有⼀个数据集&…...
面试计算机网络框架八股文十问十答第七期
面试计算机网络框架八股文十问十答第七期 作者:程序员小白条,个人博客 相信看了本文后,对你的面试是有一定帮助的!关注专栏后就能收到持续更新! ⭐点赞⭐收藏⭐不迷路!⭐ 1)UDP协议为什么不可…...
Codeforces Round 926 (Div. 2)
A. Sasha and the Beautiful Array(模拟) 思路 最大值减去最小值 #include<iostream> #include<algorithm> using namespace std; const int N 110; int a[N];int main(){int t, n;cin>>t;while(t--){cin>>n;for(int i 0; i…...
构建智慧交通平台:架构设计与实现
随着城市交通的不断发展和智能化技术的迅速进步,智慧交通平台作为提升城市交通管理效率和水平的重要手段备受关注。本文将探讨如何设计和实现智慧交通平台的系统架构,以应对日益增长的城市交通需求,并提高交通管理的智能化水平。 ### 1. 智慧…...
移动端设置position: fixed;固定定位,底部出现一条缝隙,不知原因,欢迎探讨!!!
1、问题 在父盒子中有一个子盒子,父盒子加了固定定位,需要子盒子上下都有要边距,用margin或者padding挤开时,会出现缝隙是子盒子背景颜色的。 测试过了,有些手机型号有,有些没有,微信小程序同移…...
有关网络安全的课程学习网页
1.思科网络学院 免费学习skillsforall的课程 课程链接:Introduction to Cybersecurity by Cisco: Free Online Course (skillsforall.com) 2.斯坦福大学计算机和网络安全基础 该证书对于初学者来说最有价值,它由最著名的大学之一斯坦福大学提供。您可…...
计算机网络-面试题
一、基础 1、网络编程 网络编程的本质是多台计算机之间的数据交换存在问题 如何准确的定位网络上一台或多台主机如何进行可靠传输2、网络协议 在计算机网络有序的交换数据,就必须遵守一些事先约定好的规则,比如交换数据的格式、是否需要发送一个应答信息。这些规则被称为网络…...
C++虚函数
C虚函数 在C中,虚函数(Virtual Function)是一个使用关键字virtual声明的成员函数,它在基类中被声明,以便在任何派生类中被重写(Override)。使用虚函数的目的是实现多态性——一种允许使用基类指…...
MySQL数据库基础(二):MySQL数据库介绍
文章目录 MySQL数据库介绍 一、MySQL介绍 二、MySQL的特点 三、MySQL版本 四、MySQL数据库下载与安装 1、下载 2、安装 五、添加环境变量(Windows) 六、检测环境变量是否配置成功 MySQL数据库介绍 一、MySQL介绍 MySQL是一个关系型数据库管理…...
常用文件命令
文章目录 文件命令文件内容查看catnlmoreless(more的plus版)headtailod 文件属性操作用户权限常见的权限chownchmodchgrpumask 隐藏属性常见的隐藏属性lsattrchattr 查找文件查看文件类型查找文件位置whichwhereislocatefind 文件操作(复制、…...
在屏蔽任何FRP环境下从零开始搭建安全的FRP内网穿透服务
背景 本人目前在境外某大学读博,校园网屏蔽了所有内网穿透的工具的数据包和IP访问,为了实现在家也能远程访问服务器,就不得不先开个学校VPN,再登陆。我们实验室还需要访问另一个大学的服务器,每次我都要去找另一个大学…...
OpenGL-ES 学习(1)---- AlphaBlend
AlphaBlend OpenGL-ES 混合本质上是将 2 个片元的颜色进行调和(一般是求和操作),产生一个新的颜色 OpenGL ES 混合发生在片元通过各项测试之后,准备进入帧缓冲区的片元和原有的片元按照特定比例加权计算出最终片元的颜色值,不再是新…...
Python 函数的学习笔记
Python 函数的学习笔记 0. Python 函数的概要说明1. 自定义函数示例2. 匿名函数示例3. 内置函数示例3-1. filter() 示例3-2. map() 示例3-3. reduce() 示例 4. 可变长参数*args和**kwargs示例4-1. *args(Positional Variadic Arguments)4-2. **kwargs&am…...
详解 Redis 实现数据去重
✨✨ 欢迎大家来到喔的嘛呀的博客✨✨ 🎈🎈希望这篇博客对大家能有帮助🎈🎈 目录 言 一. Redis去重原理 1. Redis Set 数据结构 2. 基于 Set 实现数据去重 3. 代码示例 4. 总结 …...
FreeRTOS 延迟中断处理
采用二值信号量同步 二值信号量可以在某个特殊的中断发生时,让任务解除阻塞,相当于让任务与中断 同步。这样就可以让中断事件处理量大的工作在同步任务中完成,中断服务例程(ISR) 中只是快速处理少部份工作。如此,中断处理可以说是…...
计网体系结构
计算机网络的概述 概念 网络:网状类的东西或系统。 计算机网络:是一个将分散的、具有独立性功能的计算机系统,通过通信设备与线路连接起来,由功能完善的软件实现资源共享和信息传递的系统。即计算机网络是互连(通过通信链路互连…...
linux系统zabbix工具监控web页面
web页面监控 内建key介绍浏览器配置浏览器页面查看方式 监控指定的站点的资源下载速度,及页面响应时间,还有响应代码; web Scenario: web场景(站点)web page :web页面,一个场景有多…...
VMware虚拟机网络配置
VMware虚拟机网络配置 桥接模式NAT网络 桥接模式 桥接模式其实就是借助你宿主机上的网卡进行联网和通信,所以相当于虚拟机和宿主机平级,处于同一个网段中。 配置要点: 注意选择正确的宿主机网卡 查看宿主机的网络信息,这些信息指…...
代码随想录算法训练营DAY18 | 二叉树 (5)
一、LeetCode 513 找树左下角的值 题目链接:513.找树左下角的值https://leetcode.cn/problems/find-bottom-left-tree-value/ 思路一:递归回溯全局变量比深度。 class Solution {int Max_depth 0;int result 0;public int findBottomLeftValue(TreeNo…...
企业微信自动推送机器人的应用与价值
随着科技的快速发展,企业微信自动推送机器人已经成为了企业数字化转型的重要工具。这种机器人可以自动推送消息、执行任务、提供服务,为企业带来了许多便利。本文将探讨企业微信自动推送机器人的应用和价值。 一、企业微信自动推送机器人的应用 企业微信…...
Matplotlib plt.plot:从入门到精通,只需一篇文章!
Matplotlib plt.plot:从入门到精通,只需一篇文章! 利用Matplotlib进行数据可视化示例 🌵文章目录🌵 📊 1. 引言:为什么Matplotlib在数据可视化中如此重要?📊✨ 2. plt.pl…...
Linux中sigaction函数和SIGCHLD信号的使用
sigaction函数: 函数说明:注册一个信号处理函数 函数原型:int sigaction(int signum, const struct sigaction *act, struct sigaction *oldact); 函数参数: signum:捕捉的信号act:传入参数,…...
【MySQL】操作库 —— 表的操作 -- 详解
一、增加表 1、创建表 mysql> create database [if not exists] table_name ( -> field1 datatype, -> field2 datatype, -> field3 datatype -> ) character set 字符集 collate 校验规则 engine 存储引擎; 注意 :最后一行也可以写成&#x…...
ZigBee学习——在官方例程实现组网
✨Z-Stack版本:3.0.2 ✨IAR版本:10.10.1 ✨这篇博客是在善学坊BDB组网实验的基础上进行完善,并指出实现的过程中会出现的各种各样的问题! 善学坊教程地址: ZigBee3.0 BDB组网实验 文章目录 一、基础工程选择二、可能遇…...
ES实战--wildcard正则匹配exists过滤字段是否存在
wildcard 通配符中的 * 表示任意数量的字符 ?表示任意单个字符 #正则匹配 GET /wildcard-test/_search {"query": {"wildcard": {"title": {"wildcard": "ba*n"}}} } #响应:"hits": {"total": {"…...
C++学习:二分查找
二分查找的前提 库函数只能对数组进行二分查找。 对一个数组进行二分查找的前提是这个数组中的元素是单调的。 一般为单调不减,当然如果是单调不增也可以(需要修改比较函数) 例如: [1,5,5,9,18]是单调的 [1 , 9, 9,…...
语言与科技创新(大语言模型对科技创新的影响)
1.语言因素对科技创新的影响 科技创新中的语言因素至关重要,具体体现在以下几个方面: 科技文献交流: 英语作为全球科学研究的通用语言,极大地推动了科技成果的国际传播与合作。在国际上,科学家们在发表论文、报告研究…...
【C语言】简单贪吃蛇实现保姆级教学!!!
关注小庄 顿顿解馋૮(˶ᵔ ᵕ ᵔ˶)ა 新年快乐呀小伙伴 引言: 小伙伴们应该都有一个做游戏的梦吧?今天让小庄来用C语言简单实现一下我们的童年邪典贪吃蛇,顺便巩固我们的C语言知识,请安心食用~ 文章目录 贪吃蛇效果一.游戏前工作…...
rtt设备io框架面向对象学习-uart设备
目录 1.uart设备基类2.uart设备基类的子类3.初始化/构造流程3.1设备驱动层3.2 设备驱动框架层3.3 设备io管理层 4.总结5.使用 1.uart设备基类 此层处于设备驱动框架层。也是抽象类。 在/ components / drivers / include / drivers 下的serial.h定义了如下uart设备基类 struc…...
Innodb下修改事务工作流程(buffer pool、redo log、undolog)
1、在Buffer Pool中读取数据:当InnoDB需要更新一条记录时,首先会在Buffer Pool中查找该记录是否在内存中。如果没有在内存中,则从磁盘读取该页到Buffer Pool中。 2、记录UndoLog:在修改操作前,InnoDB会在Undo Log中记…...
redis为什么使用跳跃表而不是树
Redis中支持五种数据类型中有序集合Sorted Set的底层数据结构使用的跳跃表,为何不使用其他的如平衡二叉树、b树等数据结构呢? 1,redis的设计目标、性能需求: redis是高性能的非关系型(NoSQL)内存键值数据…...
【matalab】基于Octave的信号处理与滤波分析案例
一、基于Octave的信号处理与滤波分析案例 GNU Octave是一款开源软件,类似于MATLAB,广泛用于数值计算和信号处理。 一个简单的信号处理与滤波分析案例,说明如何在Octave中生成一个有噪声的信号,并设计一个滤波器来去除噪声。 首…...
Elasticsearch:特定领域的生成式 AI - 预训练、微调和 RAG
作者:来自 Elastic Steve Dodson 有多种策略可以将特定领域的知识添加到大型语言模型 (LLM) 中,并且作为积极研究领域的一部分,正在研究更多方法。 对特定领域数据集进行预训练和微调等方法使 LLMs 能够推理并生成特定领域语言。 然而&#…...
HarmonyOS—UI 开发性能提升的推荐方法
开发者若使用低性能的代码实现功能场景可能不会影响应用的正常运行,但却会对应用的性能造成负面影响。本章节列举出了一些可提升性能的场景供开发者参考,以避免应用实现上带来的性能劣化。 使用数据懒加载 开发者在使用长列表时,如果直接采用…...
84 CTF夺旗-PHP弱类型异或取反序列化RCE
目录 案例1:PHP-相关总结知识点-后期复现案例2:PHP-弱类型对比绕过测试-常考点案例3:PHP-正则preg_match绕过-常考点案例4:PHP-命令执行RCE变异绕过-常考点案例5:PHP-反序列化考题分析构造复现-常考点涉及资源…...
Duilib List 控件学习
这是自带的一个示例; 一开始运行的时候List中是空的,点击Search按钮以后就填充列表框; 先看一下列表框列头是在xml文件中形成的; <List name="domainlist" bkcolor="#FFFFFFFF" ... menu="true"> <ListHeader height="24…...
详细了解Node.js的配置与使用!
详细了解Node.js的配置与使用! Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境。它允许开发者在服务器端运行 JavaScript,从而实现全栈 JavaScript 开发。本文将介绍 Node.js 的配置和 npm 的应用。 一、Node.js 配置 下载与安装 首先&…...
OpenCV 移动最小二乘图像变形
文章目录 一、简介二、实现代码三、实现效果参考文献一、简介 在现实生活中,我们常常应用一些刚性的变换来实现物体的旋转平移,对于非刚性的变换我们都没有在意,其实这种变换也是无处不在的,如我们经常看的动画就可以通过一些非刚性的变换达到一些非常夸张的效果。这里,我…...
【深度学习】S2 数学基础 P4 概率论
目录 基本概率论概率论公理随机变量 多个随机变量联合概率条件概率贝叶斯定理求和法则独立性 期望与方差小结 基本概率论 机器学习本质上,就是做出预测。而概率论提供了一种量化和表达不确定性水平的方法,可以帮助我们量化对某个结果的确定性程度。 在…...
跟我学c++中级篇——静态多态
一、多态 Polymorphism,多态。学习过c的人如果不知道多态,基本上就是打入c内部的C程序员了。在前边曾经对多态进行过分析,对其中的虚函数(虚表等)也进行过较为详细的说明。 多态其实非常好理解,不要硬扣书…...
设计模式--桥接模式(Bridge Pattern)
桥接模式(Bridge Pattern)是一种结构型设计模式,它主要是用于将抽象部分与实现部分分离,使它们可以独立地变化。 桥接模式主要包含以下几个角色: Abstraction(抽象类):定义抽象类的…...
统计图饼图绘制方法(C语言)
统计图饼图绘制方法(C语言) 常用的统计图有条形图、柱形图、折线图、曲线图、饼图、环形图、扇形图。 前几类图比较容易绘制,饼图绘制较难。今值此介绍饼图的绘制方法。 本方法采用C语言的最基本功能: ( 1.)…...
洛谷C++简单题小练习day12—寻找最小值小程序
day12--寻找最小值--2.16 习题概述 题目描述 给出 n 和 n 个整数 ai,求这 n 个整数中最小值是什么。 输入格式 第一行输入一个正整数 n,表示数字个数。 第二行输入 n 个非负整数,表示 1,2…a1,a2…an,以空格隔开。 …...
相机图像质量研究(13)常见问题总结:光学结构对成像的影响--鬼影
系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结:光学结构对成…...