当前位置 : 主页 > 编程语言 > c语言 >

数据结构 ---> 二叉树 -->堆之解析_01

来源:互联网 收集:自由互联 发布时间:2023-10-08
老友们好 !本期将对堆之构建进行解说 ! 相信,初学此章节的老友 !!或多或少,对前一期的部分代码,有所困惑! 说真的,堆的有些内容理解起来还是挺困难的! 好了,废话不多

老友们好 !本期将对堆之构建进行解说 !

相信,初学此章节的老友 !!或多或少,对前一期的部分代码,有所困惑!

说真的,堆的有些内容理解起来还是挺困难的!

好了,废话不多讲!开始本期的解析之旅吧 !希望大家都能有所收获 !!

下面,先看一组,上一期的图示:>

数据结构 ---> 二叉树 -->堆之解析_01_堆之构建解析

那么该如何操作,才能取得前几名的数值呢?

针对这点,部分老友,可能,会用数组的覆盖原理 !

即是 将堆顶元素弹出后,再找出次大的数值。这一后续过程,想到了值的覆盖原理 !那么,究竟是否正确?弊端在哪里?

下列图示,可为老友们,解答疑惑 !

数据结构 ---> 二叉树 -->堆之解析_01_向下调整算法_02

由上图可知,按照上述想到的方法,显然会出现严重的 “紊乱”现象发生!即是 父子兄弟关系,全部乱套了 !!

这样子,不仅效率低下,而且再找次大的时候,需要对剩余元素重新进行建堆 !而每一次建堆的时间复杂度是 O(N*logN)

有关于,建堆之时间复杂度,会在后续章节进行讲解 !!

而对上述问题,解决之道是封装一个函数,进行每次查找的时候

时间复杂度是 O(N) 这意味着,只需要每一次查找,遍历一遍即可,根本无须一遍又一遍的建堆操作 !!

然而这块思想逻辑的实现,是本章节的一大难点之一 !不好理解 !

下面图示,就是上一期所写就的 向上调整算法 !!

称之为算法,在这里一点儿都不过分 !!

数据结构 ---> 二叉树 -->堆之解析_01_向上调整算法_03

请注意,上述红色方框内的 条件判断 !!

而很多老友,不明白这种思想逻辑;

甚至对前面的二叉树遍历,并没有打牢基础,会很容易掉进坑里 !!

下面展现错误写法 :>

数据结构 ---> 二叉树 -->堆之解析_01_边界值问题_04

这种写法,逻辑上的漏洞是在那里?先说答案好了!

----> "parent" 与 “child” 会最终重合在一起,无法进行建大堆操作

数据结构 ---> 二叉树 -->堆之解析_01_完美特性_05

如上图所示,是小堆,然后建立大堆

若还是比较难理解,只需,将parent取特殊值检验即可

比如,令 parent = 0 ;进入循环体之后,满足条件,“孩子结点”更新为 下标是 0;此后“双亲结点”也会被更新为 下标是 0,注意取整操作,虽然 双亲结点---> parent = (0 - 1)/ 2 ---> - 1 / 2 , 取整后仍然是 0 ,此时便不符合建立大堆要求 !

现在,剖析一下,错误想法的来源,其实这才是有意思的地方 !

上一篇:【数据结构 & 空间复杂度】
下一篇:没有了
网友评论