堆的认识

简介: 堆的认识

概念


堆是一种图的数据结构,被用于实现“优先队列”。优先队列是一种数据结构,可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点(node)”,数据就存储在这些节点中。


堆的特点


如图所示,每个节点由两个子节点,用线条连接即为堆。


  • 结点内的数字就是存储的数据
  • 堆中的每个结点最多有两个子节点
  • 树的形状取决于数据的个数
  • 节点的排列顺序为从上到下,同一行里则为从左到右
  • 堆的父节点必须小于子结点


640.png


堆的数据存储


在堆中存储数据时必须遵守这样一条规则:子结点必定大于父节点


  • 顶端的结点为根节点存储的数据为堆中的最小值
  • 新数据增加时会被放在堆的最底部靠左的位置
  • 堆的底部没有多余空间时,会另起一行把数据加在这一行的最左端


例如,将数字5添加到堆中


640.png



  • 结点6有个空位置,将数字5加在结点6中



640.png

  • 数字5结点的父结点大于本身,故调换位置


640.png


  • 交换完毕后数字5结点的父节点小于本身,所以不再交换,往堆中插入数据5的操作结束


640.png


堆的数据获取


从堆中获取数据时,需要从最上面的数据开始取,取完数据后,堆需要进行重新排序,将最后的数据移到取出的结点位置。


如图所示,取出堆中的数字1。


640.png


  • 1被取出后,结构需要重新调整


640.png


  • 将最后的数字6结点移到最顶部


640.png


  • 如果子结点的数字小于父节点,就将父节点与其左右两个子节点中较小的一个进行交换


640.png


  • 数字6结点的子结点3和5,3为较小者。故与3进行位置调换


640.png


  • 交换后,数字6结点的两个子节点4和8,4为较小者。故与4进行位置交换


640.png


  • 交换后,数字6结点无子节点。故交换完毕,从堆中取出数据的操作完成


640.png


写在最后


  • 文中使用的图片源自《我的第一本算法书》,如若侵权,请评论区留言,作者立即删除相关图片。
  • 公众号无法外链,如果文中有链接,可点击下方阅读原文查看😊
相关文章
|
SQL 数据格式
视图有哪些特点?哪些使用场景?
视图有哪些特点?哪些使用场景?
|
6月前
|
机器学习/深度学习 存储 算法
【LeetCode 热题100】347:前 K 个高频元素(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 347——前 K 个高频元素的三种解法:哈希表+小顶堆、哈希表+快速排序和哈希表+桶排序。每种方法都附有清晰的思路讲解和 Go 语言代码实现。小顶堆方法时间复杂度为 O(n log k),适合处理大规模数据;快速排序方法时间复杂度为 O(n log n),适用于数据量较小的场景;桶排序方法在特定条件下能达到线性时间复杂度 O(n)。文章通过对比分析,帮助读者根据实际需求选择最优解法,并提供了完整的代码示例,是一篇非常实用的算法学习资料。
350 90
|
9月前
|
存储 NoSQL 关系型数据库
【赵渝强老师】什么是NoSQL数据库?
随着大数据技术的兴起,NoSQL数据库(Not Only SQL)得到广泛应用。它不局限于二维表结构,允许数据冗余。常见的NoSQL数据库包括Redis、MongoDB和HBase。Redis是基于内存的高性能数据库,采用单线程模型和多路复用I/O,支持高效的数据结构。MongoDB使用BSON格式存储文档,查询语言强大,类似关系型数据库。HBase基于HDFS,适合数据分析,采用列式存储,支持灵活的列族设计。视频讲解及更多内容见下文。
450 79
|
9月前
|
安全 Java 数据安全/隐私保护
springSecurity学习之springSecurity过滤web请求
通过配置 Spring Security 的过滤器链,开发者可以灵活地管理 Web 请求的安全性。理解核心过滤器的作用以及如何配置和组合这些过滤器,可以帮助开发者实现复杂的安全需求。通过具体的示例代码,可以清晰地了解 Spring Security 的配置方法和实践。
405 23
|
Linux 开发工具 git
使用通义灵码,参与开源项目全程纪实
我借助通义灵码完成了 obdiag 项目的第一个 PR,成为了 obdiag 项目的 contributor,我知道通义灵码的能力还远没有发挥出来,今后继续探索,未来可期。
309 11
|
存储 JSON Kubernetes
基于 cri-dockerd 二进制部署 kubernetest-v1.26.3 2
基于 cri-dockerd 二进制部署 kubernetest-v1.26.3
196 0
|
Linux 调度
Linux源码阅读笔记05-进程优先级与调度策略-实战分析
Linux源码阅读笔记05-进程优先级与调度策略-实战分析
|
敏捷开发 缓存 Java
阿里云云效产品使用合集之如何配置流水线里的npm构建
云效作为一款全面覆盖研发全生命周期管理的云端效能平台,致力于帮助企业实现高效协同、敏捷研发和持续交付。本合集收集整理了用户在使用云效过程中遇到的常见问题,问题涉及项目创建与管理、需求规划与迭代、代码托管与版本控制、自动化测试、持续集成与发布等方面。
|
SQL Go 数据库
Django入门到放弃之ORM多表操作
Django入门到放弃之ORM多表操作
|
弹性计算 安全 前端开发
阿里云服务器ECS通用型、计算型和内存实例区别、CPU型号、性能参数表
阿里云ECS实例有计算型(c)、通用型(g)和内存型(r)系列,区别在于CPU内存比。计算型1:2,如2核4G;通用型1:4,如2核8G;内存型1:8,如2核16G。实例有第五代至第八代,如c7、g5、r8a等,每代CPU型号和主频提升。例如,c7使用Intel Ice Lake,g7支持虚拟化Enclave。实例性能参数包括网络带宽、收发包能力、IOPS等,适合不同场景,如视频处理、游戏、数据库等
692 0