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

7.(数据结构)堆

7.1 相关概念

        堆(Heap)在计算机科学中是一种特殊的数据结构,它通常被实现为一个可以看作完全二叉树的数组对象。以下是一些关于堆的基本概念:

数据结构:

        堆是一个优先队列的抽象数据类型实现,通过完全二叉树的逻辑结构来组织元素。
完全二叉树意味着除了最后一层外,每一层都被完全填满,并且最后一层的所有节点都尽可能地集中在左边。
物理存储:

        堆用一维数组顺序存储,从索引0开始,每个节点的父节点和子节点之间的关系可以通过简单的算术运算确定。
堆的特性:

        堆序性质:对于任意节点i,其值(或关键字)满足与它的子节点的关系——在最大堆(大根堆)中,节点i的值大于或等于其两个子节点的值;在最小堆(小根堆)中,节点i的值小于或等于其两个子节点的值。
结构性:堆始终保持完全二叉树的状态,这意味着即使有节点删除或插入,堆也要经过调整以保持堆序性质。
操作:

        插入:新元素添加到堆中时,需要自下而上调整堆,以确保新的元素不会破坏堆的性质。
        删除:通常从堆顶(根节点)删除元素(即最大堆中的最大元素或最小堆中的最小元素),然后将堆尾元素移动到堆顶,再自上而下调整堆。
        查找:堆常用于快速找到最大或最小元素,但查找特定值的时间复杂度通常不优于线性时间,因为堆本身不具备随机访问的能力。
应用:

        堆常用于解决各种问题,如优先级队列、事件调度、图算法中的最短路径计算(Dijkstra算法)、求解Top K问题等。
分类:

        最常见的堆是二叉堆,包括大根堆和小根堆。
        还有其他类型的堆,比如斐波那契堆,提供更高效的合并操作以及其他优化特性。

建堆算法:

       1. Dijkstra算法:是一个使用优先队列(可以基于堆实现)的经典例子。在Dijkstra算法中,每次都会从未确定最短路径且当前距离已知最小的顶点开始,更新与其相邻顶点的距离。为了高效地找到下一个待处理的顶点(即当前已知最短路径的顶点),会用到一个能够根据顶点距离值进行快速插入和删除的优先队列,堆就是实现这种功能的理想数据结构之一。

       2. 堆下沉”(Heap Sink),“堆下滤”(Heap Percolate Down):从根节点(非叶子节点中最高层的一个)开始。 检查该节点与其两个子节点的关系:在最大堆中,如果当前节点的值小于其任意一个子节点的值;在最小堆中,如果当前节点的值大于其任意一个子节点的值。 如果违反了堆的性质,则交换当前节点与其较大(对于最大堆)或较小(对于最小堆)子节点的值,并将当前节点移动到新位置(即原来子节点的位置)。 重复上述步骤,但这次以交换后的子节点作为新的当前节点,继续下潜至当前节点没有子节点(即成为叶子节点),或者当前节点及其子节点均满足堆的性质为止。

时间复杂度:

相关文章:

7.(数据结构)堆

7.1 相关概念 堆(Heap)在计算机科学中是一种特殊的数据结构,它通常被实现为一个可以看作完全二叉树的数组对象。以下是一些关于堆的基本概念: 数据结构: 堆是一个优先队列的抽象数据类型实现,通过完全二叉树…...

AWS Elastic Beanstalk通过应用负载均衡配置https

接上一篇,今天说说怎么通过AWS Elastic Beanstalk提供的应用负载均衡配置https。 首先创建应用和环境,这里应用可以使用上一篇文章中使用的demo应用(只需要package.json和app.js文件) 创建环境的时候,确认下面两个参…...

AC自动机:文本搜索的加速器

在数字化时代,文本数据的海洋浩瀚无垠。我们经常需要在这些数据中迅速找到特定的信息,比如在日志文件中查找异常、在海量文本中检索关键词,或是在编译代码时识别语法结构。这时候,AC自动机(Aho-Corasick自动机&#xf…...

备战蓝桥杯---基础算法刷题1

最近在忙学校官网上的题,就借此记录分享一下有价值的题: 1.注意枚举角度 如果我们就对于不同的k常规的枚举,复杂度直接炸了。 于是我们考虑换一个角度,我们不妨从1开始枚举因子,我们记录下他的倍数的个数sum个&#…...

探索 Flutter 中的动画:使用 flutter_animate

在移动应用开发中,动画是提升用户体验和吸引用户注意力的关键要素之一。Flutter 作为一种跨平台的移动应用开发框架,提供了丰富而灵活的动画支持。其中,flutter_animate 是一个强大的库,它为 Flutter 开发者提供了简单易用的方式来…...

装机容量对光伏发电量的影响有多大?如何通过装机容量计算发电量?

光伏行业得益于全球对环保和可持续发展的重视,得到了快速的发展。众所周知,光伏电站的收益受发电量的影响,发电量越大收益越高,但发电量其实受装机容量的影响。 一、装机容量对发电量的影响 光伏发电的核心就是发电板&#xff0…...

软考37-上午题-【数据库】-数据模型、数据库的三级模式和二级映像

一、考情简介 上午题:6分——6道选择题 下午题:15分——一道分析题 E-R图、关系模式:下午考试必考!!!(编制也要考!) 二、数据模型 数据模型是对现实世界数据特征的抽象…...

06 分频器设计

分频器简介 实现分频一般有两种方法,一种方法是直接使用 PLL 进行分频,比如在 FPGA 或者 ASIC 设计中,都可以直接使用 PLL 进行分频。但是这种分频有时候受限于 PLL 本身的特性,无法得到频率很低的时钟信号,比如输入 …...

力扣hot100题解(python版7-9题)

7、接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,…...

ECMAScript 6+ 新特性 ( 四 ) 迭代器 与 生成器

2.14.迭代器 2.14.1.for…of for...of 是 JavaScript ES6 引入的一种新的循环结构,,用于遍历可迭代对象(Iterable objects)的每个元素。 它可以自动调用目标对象的迭代器接口,并按顺序逐个访问集合中的每个值。 它…...

【MySQL】事务的一致性究竟怎么理解?

众所周知,事务有四大特性:原子性、一致性、隔离性、持久性,除了一致性,其他三类特性都很好理解。而关于一致性的解释有点让人头疼,我查了很多文章,大多类似:事务的执行必须使数据库处于一致状态…...

证件照(兼容H5,APP,小程序)

证件照由uniappuyui开发完成&#xff0c;并同时兼容H5、App、微信小程序、支付宝小程序&#xff0c;其他端暂未测试。 先看部分效果图吧具体可以下方复制链接体验demo 首页代码 <template><view class""><view class"uy-m-x-30 uy-m-b-20"…...

pytorch-textregression,中文文本回归实践,支持多值输出

pytorch-textregression&#xff0c;中文文本回归实践&#xff0c;支持多值输出 pytorch-textregression是一个以pytorch和transformers为基础&#xff0c;专注于中文文本回归的轻量级自然语言处理工具&#xff0c;支持多值回归等。 目录 数据使用方式paper参考 项目地址 py…...

go语言学而思【持续更新】

问题&#xff1a;在Go语言中nil是什么意思&#xff1f; 答&#xff1a;在Go语言中&#xff0c;nil是一个预声明的标识符&#xff0c;用于表示某些类型的零值。它可以被用作以下类型的零值&#xff1a; 指针&#xff08;Pointer&#xff09;切片&#xff08;Slice&#xff09;…...

LVS-NAT之VMNET环境搭建

目录 搭建拓扑图 搭建规划 VMNET0 搭建 VMNET2 搭建 LVS端增加网卡 搭建拓扑图: 搭建规划: CLIENT(servera): VMNET0 LVS(serverb): VMNET0 VMNET2 WEB1(serverd): VMNET2 WEB2(servere): VMNET2 VMNE…...

[TCP] TCP/IP 基础知识词典(2)

我想统计一下&#xff0c;TCP/IP 尤其是TCP协议&#xff0c;能搜到的常见的问题&#xff0c;整理起来&#xff0c;关键词添加在目录中&#xff0c;便于以后查阅。 目前预计整理共3篇&#xff1a; [TCP] TCP/IP 基础知识问答 &#xff1a;基础知识 [TCP] TCP/IP 基础知识问答&…...

【牛牛送书 | 第四期】《高效使用Redis:一书学透数据存储与高可用集群》带你快速学习使用Redis

前言&#xff1a; 当今互联网技术日新月异&#xff0c;随着数据量的爆炸式增长&#xff0c;如何高效地存储和管理数据成为了每个公司都必须面对的挑战。与此同时&#xff0c;用户对于应用程序的响应速度和稳定性要求也越来越高。在这个背景下&#xff0c;Redis 作为一个…...

Threejs 实现3D影像地图,Json地图,地图下钻

1.使用threejs实现3D影像地图效果&#xff0c;整体效果看起来还可以&#xff0c;底层抽象了基类&#xff0c;实现了通用&#xff0c;对任意省份&#xff0c;城市都可以只替换数据&#xff0c;即可轻松实现效果。 效果如下&#xff1a; 链接https://www.bilibili.com/video/BV1…...

根据Excel创建管道系统及材质

之前看过程鑫老师的文章&#xff0c;介绍过根据Excel数据创建管道系统&#xff0c;但是有小伙伴问过我&#xff0c;照着他这个做&#xff0c;没成功&#xff0c;于是呢&#xff0c;我就想试下&#xff0c;结果发现也没成功。 然后我逐个节点过了一遍&#xff0c;发现可能是因为…...

第八篇【传奇开心果系列】python的文本和语音相互转换库技术点案例示例:Google Text-to-Speech虚拟现实(VR)沉浸式体验经典案例

传奇开心果博文系列 系列博文目录python的文本和语音相互转换库技术点案例示例系列 博文目录前言一、雏形示例代码二、扩展思路介绍三、虚拟导游示例代码四、交互式学习示例代码五、虚拟角色对话示例代码六、辅助用户界面示例代码七、实时语音交互示例代码八、多语言支持示例代…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...