| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 【化解数据结构】详解堆结构,并实现最小堆结构 -> 正文阅读 |
|
[数据结构与算法]【化解数据结构】详解堆结构,并实现最小堆结构 |
欢迎大家关注本专栏,持续关注最新文章~ 本专栏的其他内容 从这里开始 👉 【化解数据结构】从这里开启数据结构和算法 队列 👉【化解数据结构】详解队列,优先队列,循环队列,并实现一个队列 💡 知识点抢先看
📢碎碎念
一、什么是堆结构?你可能会知道在内存中有栈和堆之分,但是这里堆和内存中的堆不一样,这里的堆是一种数据存储的方式 堆实际上是一种特殊的队列:优先队列,关于优先队列在队列文章中已经有讲过。也就是队列中有很多待执行的任务,执行时会根据优先级来执行,优先级高的会先被执行 这也可以很容易理解,比如医院急诊室里就有对病患的优先级之分,医生会优先处理病情严重的患者,再处理相较弱的患者 对于堆而言它是一种抽象的数据结构,或者说逻辑上的数据结构,并不是物理上真实存在的数据结构 在这里我们主要讨论的是二叉堆这种最常见的结构,它是用一棵完全二叉树来实现的 对于二叉树,我们在上一篇也有涉及,它是采用数组来实现的 因此二叉堆实际也是使用数组来实现的 那么什么是完全二叉树呢? 完全二叉树和满二叉树又类似,我们先来看看什么是满二叉树 1. 满二叉树树中除了叶子节点,每个节点都有两个子节点
因此对于满二叉树的节点而言,它的度要么是 0,要么是 2,也就是要么有 2 个子节点,要么是叶子节点 如图就是一个满二叉树 2. 完全二叉树在满二叉树的性质上,最后一层的叶子节点,均在左树上
如图一棵完全二叉树 它们的区别:
3. 堆的特点好了了解了什么是完全二叉树,那堆有什么特点呢?
左边是一个最大堆,所有的子节点都小于父节点 二、如何能够实现一个堆结构呢?在 在这里选用数组来实现一个堆 利用广度优先遍历,将树填入数组里,这样我们就能用一个数组来表示一个堆了 小秘诀
因此我们不仅能够使用数组来表示一个堆,我们还能获取任意一个节点在数组中的位置,接下来我们就实现一个最小堆 三、堆中有哪些方法?我们给堆添加一些方法,一遍它在插入时,能插到准确的位置,删除时,其他的元素也能进行合理的移动
四、手写实现一个最小堆在前面我们已经知道了最小堆的定义,它的所有节点都小于等于它的子节点,因此我们根据这个特性,以及3个小秘诀来实现一个最小堆 1. 创建一个 MinHeap 类利用数组来实现一个堆类
2. 实现 swap 方法我们需要维护一个堆结构,在元素插入删除的时候,常常需要进行位置的变化,因此我们需要通过交换位置来实现 封装一个
在这里采用数组解构的方式来赋值,看着舒服一点 3. 实现 getParentIndex 方法
根据上面的小秘诀:父节点的位置是 在这里我们采用二进制的方式来取值
4. 实现 getLeftIndex 方法同样的根据秘诀:左侧子节点在数组中的位置是
5. 实现 getRightIndex 方法右侧子节点在数组中的位置是
6. 实现 shirtUp 方法这个方法是实现最小堆的关键之一,在我们插入元素时,需要对元素进行判断,我们需要将插入的元素移到符合它的位置 如何实现呢?采用递归
7. 实现 insert方法在写好了上移
来看看在一个堆中插入元素是如何运作的吧,这是一个最大堆中的动图,最小堆也一样
8. 实现 pop 方法为什么需要有下移的方法,当我们直接删除堆顶时,会导致整个堆的结构的变化,使得大小关系转变,难以操作 因此我们在删除堆顶时,只需要用数组尾部的元素,替换堆顶元素,这样改变的就只有首尾两个元素,我们再对堆顶进行下移判断,这样通过不断地交换,就能实现最小堆
9. 实现 shirtDown 方法接下来我们实现最为关键的下移代码,如何实现呢?
我们来看看删除堆顶时会发生什么? 10. 实现 peek 方法返回堆顶元素,也就是堆的最小值,数组的第一位
11. 实现 size 方法最后,实现最简单的方法,通过数组的
12. 完整的 MinHeap 类
五、LeetCode 实战在前端世界中,堆也有它的应用场景,它能够高效的找到最大值,最小值,时间复杂度为 利用堆结构,我们可以轻松解决找出最大、最小元素、第 K 大元素登问题,但远不止于这些 几道 215. 数组中的第K个最大元素347. 前 K 个高频元素1046. 最后一块石头的重量703. 数据流中的第 K 大元素📖 总结在这篇文章中我们详细讲解了,什么是一个堆,如何实现一个堆,到最后手写封装了一个最小堆,在这过程中我们知道了如何将一个元素插入堆中,如何获取堆中的特定元素。 在我们实际的堆应用当中,或者算法题当中,不一定需要将整个堆结构都实现,我们只需要实现特定的部分就可以了,不然光封装一个堆的时间都够一壶茶了,因此学习数据结构和算法,我们更多的是学习它里面的思想,对于一个堆,不过只是 “数组”而已 本文关于堆的内容就到这里结束了,相信你一定能从中学到很多东西。下一篇文章将带你探索图的奥秘。
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 | -2024/11/26 14:38:38- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |