首页 > 其他分享 >【数据结构】二叉树——堆

【数据结构】二叉树——堆

时间:2024-11-03 22:21:01浏览次数:3  
标签:孩子 建堆 二叉树 向下 数据结构 我们 调整

一、二叉树的概念与结构

二叉树的概念

二叉树是树的一种,二叉树的特殊之处在于,每个根节点都可以有两个子节点,可以两个子节点都为空,或者一个为空,一个不为空,或者两个都有数,在构建二叉树的节点时就可以看出:
在这里插入图片描述
现实中的二叉树:
在这里插入图片描述
就像这颗树,每次分叉都分出两个枝条,这就是一个二叉树
在这里插入图片描述

特殊的二叉树

完全二叉树

完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

满二叉树

满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是,则它就是满二叉树。

在这里插入图片描述

二、特殊的二叉树——堆

2.1 堆的定义

首先堆是一个完全二叉树,堆中的数字要以一定的规则进行排列
如果我们创建一个堆
让堆中所有根部数据都小于该根的左右两孩子的数据,那么这个就是一个小堆
让堆中所有根部数据都大于该根的左右两孩子的数据,那么这个就是一个大堆
在这里插入图片描述
所以我们可以理解为,若堆第一层根部为整个堆的最大值,为大堆,若为整个堆的最小值,为小堆

2.2 堆的结构

我们知道了堆的定义那我们如何队堆进行创建以及存储呢?
有两个方案:顺序结构存储,链式结构存储

顺序结构存储

我们要定义父母节点和孩子节点
父母数组下标:
parent = (child - 1) / 2
孩子数组下标:
左孩子:child = parent * 2 + 1
右孩子:child = parent * 2 + 2
在这里插入图片描述

在这里插入图片描述

如图我们将二叉树通过顺序表,也就是数组存储
优点:有下标查找数据方便
缺点:有可能会出现空的情况浪费空间,在顺序表开辟空间时一次开辟二倍,会造成空间浪费

链式结构存储

在这里插入图片描述
我们像上面开辟二叉树的节点,分为根节点,左孩子节点,右孩子节点
优点:随用随开,不会有空间浪费
缺点:无法随意访问树中元素,只能遍历

总结

对于堆这种特殊二叉树来说,因为堆是完全二叉树,所以不存在中间有用不到的空间,所以对于创建堆这个特殊结构,我们选择采用顺序结构存储。

2.3 堆的代码实现

堆的结构体创建

在这里插入图片描述

堆的初始化

在这里插入图片描述
先判断传过来的是否为空指针,若为空指针则下面无法解引用,会使程序出错
在初始化阶段可以选择先开辟空间,比如先开辟四个空间,但是在插入时也会开辟空间,会有一些重复,我就没有选择开辟。

堆的销毁

因为我们要动态开辟空间,所以为了避免出现内存泄漏,我们要将开辟的空间进行释放
在这里插入图片描述
这里我们不能直接 free(php) 因为堆中还有我们开辟的数组,如果直接释放,就会使内存泄漏,并且使程序中出现野指针。
在这里插入图片描述

堆的插入

在将堆插入时我们要考虑以下一些问题:
1、是否需要为插入数据开辟空间
2、当数据插入堆时,我们需要对堆进行调整

问题1

解决问题1,我们要先将 size 与 capacity 进行比较,若相等说明需要开辟空间
在这里插入图片描述

问题2

解决问题2,我们要将插入的数进行向上调整,我们传进去的是孩子所在下标,我们要找到其父母下标,向上调整对多的情况是插入的数为最小值到了下标为0的位置。

我们写一个向上调整函数:
传入的是数组,和要向上调整的孩子节点。
在这里插入图片描述

堆的删除

这里的删除并不是将最后一个数删除,而是将下标为0位置的根删除,这就会引发一系列问题:
如何删除,是通过将后面的数据把根位置的数据覆盖吗?如果如此做的话,后面的数就不是堆了,还要重新建堆,这未免有些不合适。
在这里插入图片描述
如果删除之后要重新建堆,效率就会变得很低。

所以我们若要删除根位置节点,就不能直接删除
我们采用的方法是将数组末尾的数与根位置的节点进行交换,然后删除数组末尾的数据,因为根的两个子树没有变,所以两个子树还是堆,将根位置交换过去的数进行向下调整
向下调整:
向下调整和向上调整相反
向上调整是将数据从孩子向上与父母比
向下调整时将数据从父母向下与孩子比
若是小堆,向下调整时要与孩子中小的那一个进行比较,因为若是与两个孩子中较大的那一个进行比较有可能较大的孩子大于另外一个孩子而小于父亲,当这个孩子被换到上面时就会出错。
在这里插入图片描述

我们将数组传过去,将数组的数量传过去,再将数组的父母下标传过去,然后找到自己两孩子中小的孩子,与最小的孩子进行比较,交换之后,再让父母到孩子位置,孩子到他们孩子的小的孩子的位置,再进行比较,直到孩子到数组大小边界,循环停止。
在这里插入图片描述

在这里插入图片描述

取堆顶数据

在这里插入图片描述

堆的数据个数

在这里插入图片描述

判断堆是否为空

在这里插入图片描述

总结

堆的全部代码
在做出的堆之后,我们要明白我们为社么要创建堆,明白为什么要做那么多接口,以及堆的应用场景。

三、如何建堆

向上调整建堆

向上建堆很好理解,我们之前写的向上调整函数,我们将数组中每个元素都进行一次向上调整,相当于每次循环都将数组中的数插入,向上调整,成功建堆。
在这里插入图片描述

向下调整建堆

向下调整建堆,我们想如果我们能从下标为0开始直接向下调整就很方便,但是我们不能保证下标为0的位置下面它的孩子是堆,所以我们要想向下调整建堆,我们要让下面每一个子树都是堆,那我们从最后一个孩子开始找他的父亲让他们先建堆,然依次让每个父母位置都向下调整,最后就可以成功建堆。
在这里插入图片描述
在这里插入图片描述

向上调整建堆与向下调整建堆的效率区别

既然有两种建队方法,那具体哪一种建堆方法更好呢?

向上调整

在这里插入图片描述
最大调整次数指的是,该层数据向上调整时,最多会调整多少次,就比如第一层,数最多调整 0 次,因为此时堆中就只有一个,
第二层,数最多调整 1 次
依次类推……
第 h 层,数最多调整 h - 1 次

向下调整

在这里插入图片描述
第 h 层,数最多向下调整 0 次,因为他们下面没有数
第 h - 1 层,数最多向下调整 1 次
依次类推……
第一层, 数最多向下调整 h - 1次

总结

根据上面我们发现,在堆中
向上调整:
当数越时,调整次数越
当数越时,调整次数越
向下调整:
当数越时,调整次数越
当数越时,调整次数越

在这里插入图片描述
而且对于这个每层数据个数都是前一个层数据个数的二倍的结构来说,这个数据处理量的差别是很大的。

在这里插入图片描述
根据错位相减,得到数据个数的总数,我们可以发现第 h 层几乎占了数据个数的 50%
所以我们得出结论,向下调整建堆比向上调整建堆效率要高很多

四、堆排序

前面我们知道了堆如何创建,如何建堆,那我们建堆有什么用呢?
我们发现不管是大堆还是小堆,在下标为 0 的位置一定是数组中的最大或者最小值,那么我们就可以依据此进行排序操作。
在这里插入图片描述

当我们要排序降序时,我们将第一个数与最后一个数进行交换,这个最小的数就到了最后,然后再对剩下的数进行向下调整,然后再循环此操作,最后就可以得到降序的数组。
升序时建大堆,再进行此操作。

堆排序的效率非常高,但是对有很多重复数据的数组排序速度会低一些

标签:孩子,建堆,二叉树,向下,数据结构,我们,调整
From: https://blog.csdn.net/2302_79968411/article/details/143302964

相关文章

  • 二叉树进阶-二叉搜索树
    目录1.二叉树的概念2.二叉搜索树的操作2.1二叉搜索树的结构2.2实现节点的查找(find)2.3实现增加节点(insert)2.4实现删除节点(erase)2.5析构函数2.6二叉搜索树的完整实现3.二叉搜索树的应用3.1K模型3.2KV模型4.二叉搜索树的性能分析1.二叉树的概念二叉搜索树也叫二......
  • 五、数据结构与算法
    五、数据结构与算法注意:本文章学习了zst_2001大佬的视频。本人亲自写的笔记。其中部分图片是结合了给位大佬的笔记图片整理的。目的是为了帮助速记。不喜勿喷1、时间空间复杂度排序1、时间复杂度O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n^3)加法:相加,保留最高项系数化......
  • Redis的ZSet底层数据结构,ZSet类型全面解析
    文章目录一、ZSet有序集合类型1.1简介1.2应用场景1.3底层结构1.4ZSet常用命令二、ZSet底层结构详解2.1数据结构2.2压缩列表ZipList2.3跳表详解2.3.1跳表是什么(what)2.3.2跳表怎么做的(how)2.3.3为什么需要跳表(WHY)/跳表高效的动态插入和删除2.3.4ZSet中的跳表2.4什么时候采......
  • 数据结构模拟题[十]
    数据结构试卷(十)一、选择题(24分)1.下列程序段的时间复杂度为()。i=0,s=0;while(s<n){s=s+i;i++;}(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)O(n2)2.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列()存储方式最节省运算时间。(A)单向链表(B)单向循......
  • 代码随想录算法训练营第十五天|leetcode110. 平衡二叉树、leetcode257.二叉树的所有路
    1leetcode110.平衡二叉树题目链接:110.平衡二叉树-力扣(LeetCode)文章链接:代码随想录视频链接:后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树_哔哩哔哩_bilibili1.1视频看后的思路1.1.1完整的代码就是不断判断,对其数据存储,其实突然发现每道题思路真的都很像,就......
  • C++——二叉树(进阶)
    1.二叉搜索树1.1概念二叉搜索树又称二叉排序树,它或是一棵空树,又或是具有以下性质的二叉树:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值若它的右子树不为空,则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二......
  • 【模板】手写基本数据结构
    栈STL模板STL中的stack容器提供了一众成员函数以供调用,常见的包括但不限于如下:创建一个栈:stack<int>stk;修改元素:stk.push(x);将传入的参数插入到栈顶。stk.pop();将栈顶的元素弹出。查询:stk.top();返回栈顶的元素。stk.empty();返回栈是否为空。stk.size......
  • Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
    文章目录一、Redis数据结构概述1.1Redis有哪些数据类型1.2Redis本质是哈希表1.3Redis的哈希冲突与渐进式rehash1.4数据结构底层1.4.1简单动态字符串SDS1.4.2双向链表LinkedList(后续已废弃)1.4.3压缩列表ZipList1.4.4哈希表HashTable1.4.5跳表SkipList1.4.6......
  • [Flag] 数据结构
    本人在11.3日立下此Flag,励志NOIP前学完所有常用数据结构,望周知。NOIP不行就省选标蓝为基本掌握,标红为完全掌握并且可以熟练运用,标黑为未掌握。目标:全部标蓝,1/3标红。堆左偏树配对堆分块分块ST表ST表树状数组区修区查树状数组二......
  • Redis数据结构:List类型全面解析
    文章目录一、List数据类型1.1简介1.2应用场景1.3底层结构二、数据结构2.1压缩列表ZipList2.2双向链表LinkedList(后续已废弃)2.3快速链表QuickList三、List常见命令一、List数据类型1.1简介详细介绍:Redis五种数据类型、String、List、Set、Hash、ZSetRedis......