当前位置:   article > 正文

【tree】二叉堆(大顶堆或小顶堆)

二叉堆

本文目录

  • 一、二叉堆的定义
    • 结构性质
    • 堆序性质
  • 二、二叉堆的底层存储结构
  • 三、二叉堆的插入
  • 四、二叉堆的删除
  • 五、源码和测试

系列目录


一、二叉堆的定义

二叉堆:首先是一棵二叉树,其次这棵二叉树要满足结构性质和堆序性质

  • 结构性质:是一颗完全二叉树
  • 堆序性质:
    • 大顶堆:对于树中的任意节点,要求key大于等于它的两个孩子,两个孩子之间没有排序要求,所以根节点拥有最大值
    • 小顶堆:对于树中的任意节点,要求key小于等于它的两个孩子,两个孩子之间没有排序要求,所以根节点拥有最小值

二叉堆常常用来实现优先级队列,在JDK的定时任务java.util.Timer中,就通过一个小顶堆TaskQueue来存放定时任务TimerTask。

1.结构性质

二叉堆是一颗完全二叉树

完全二叉树:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

这个定义看了就像没看一样,我们讲点通俗易懂的。

满二叉树每一层的节点都是满的:

  • 第零层只有根节点,所以有2^0=1个节点
  • 第一层有2^1=2个节点
  • 第二层有2^2=4个节点
  • 第三层有2^3=8个节点
  • ......

如果一棵二叉树每一层的节点都是满的,这棵树就是满二叉树。下图就是一颗满二叉树。

满二叉树一定是一颗完全二叉树,但完全二叉树不一定是一颗满二叉树。

完全二叉树结构上很接近满二叉树,只是允许最后一层不满,并且中间不允许空洞。

下图就是一颗完全二叉树,中间没有空洞,虽然最后

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/634979
推荐阅读
相关标签
  

闽ICP备14008679号