绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
图解二叉堆(最小堆&最大堆)
2020-06-02 11:07:28

二叉堆

二叉堆是一颗完全二叉树,该树中的某个节点的值总是不大于(不小于)其左右子节点的值,包括最小堆和最大堆。可以通过下图理解,为什么会使用数组来保存呢?因为利用完全二叉树的性质,我们可以通过数组来表示完全二叉树(数组下标与完全二叉树节点存在映射关系,比如父节点可以通过Math.floor((index-1)/2)来获取、左子节点可以通过2index+1来获取、右子节点可以通过2index+2来获取,从而简化了实现及开销,避免使用额外的指针来实现树结构。


最小堆

最小(大)堆性质

  • 树根节点的值是所有堆节点值中最小(大)值。

  • 树中每个节点的子树也都是最小(大)堆。

最小(大)堆作用

最小(大)堆能保证堆顶元素为最小,而如果使用数组无法达到该效果。数组如果要访问最小值则需要遍历查找最小值,时间复杂度至少O(n)。而最小堆访问最小值时间复杂度为O(1),当然天底下没有免费的午餐,我们需要做额外的工作去维护最小(大)堆的结构,这也是需要复杂度花销的。

当然这也是最小(大)堆的优势,通过动态维护使得最小值的获取代价很小,实际上维护的时间复杂度为O(logN)。而数组则无法做到如此,如果数组想要维护顺序性则需要的复杂度至少为O(N)。这样来看最小(大)堆的优势就凸现出来了。

插入操作

为避免冗长累赘,我们这里只挑最小堆作为例子进行说明,最大堆的情况与最大堆相似。

现在分别插入4 7 2 5 6 1 0 3 8,使用一个数组来保存最小堆。为了帮助理解,数组下方提供一个逻辑上的完全二叉树的结构,两者结合着更容易理解其中机制。首先插入4。

image

接着插入7,插入后检测到树符合最小堆要求,所以不改动。

继续插入2,插入后检测到不符合最小堆要求,父节点4大于右子节点2。

于是将它们对调。

继续插入5,插入后检测到不符合最小堆要求,父节点7大于左子节点5。

于是将它们对调。

继续插入6,插入后检测到树符合最小堆要求,所以不改动。

继续插入1,插入后检测到不符合最小堆要求,父节点4大于左子节点1。

于是将它们对调。

对调后继续检测到不符合最小堆要求,父节点2大于右子节点1。

继续将它们对调。

继续插入0,插入后检测到不符合最小堆要求,父节点2大于右子节点0。

于是将它们对调。

对调后继续检测到不符合最小堆要求,父节点1大于右子节点0。

继续将它们对调。

继续插入3,插入后检测到不符合最小堆要求,父节点7大于左子节点3。

于是将它们对调。

对调后继续检测到不符合最小堆要求,父节点5大于左子节点3。

继续将它们对调,然后符合最小堆要求,不必继续往上对调。

继续插入8,插入后检测到树符合最小堆要求,所以不改动。以上,完成所有元素的最小堆插入操作。

min heap21

删除操作

删除操作其实就是删除最小值,即最小堆树中的根节点。主要是将树中最后一个节点替换到被删除的根节点,然后自顶向下递归调整使之符合最小堆要求。

删除根节点0,然后将树的最后一个节点8补到根节点上。

比较根节点的左右子节点。

因为右子节点1比较小,所以我们要进一步比较的是根节点8与右子节点1。

1小于8,于是对调。

继续比较现在节点8的左右子节点。

因为右子节点2比较小,所以我们要进一步比较的是根节点8与右子节点2。

2小于8,于是对调。

至此,完成最小值删除操作。


本公众号专注于人工智能、读书与感想、聊聊数学、计算机科学、分布式、机器学习、深度学习、自然语言处理、算法与数据结构、Java深度、Tomcat内核等。

作者简介:笔名seaboat,擅长人工智能、计算机科学、数学原理、基础算法。出版书籍:《Tomcat内核设计剖析》、《图解数据结构与算法》、《人工智能原理科普》。

支持作者,购买作者书籍!


分享好友

分享这个小栈给你的朋友们,一起进步吧。

远洋号
创建时间:2020-05-19 15:46:16
《图解数据结构与算法》《Tomcat内核设计剖析》书籍作者,公众号:《远洋号》,笔名:seaboat,擅长工程算法、人工智能算法、自然语言处理、架构、分布式、高并发、大数据、搜索引擎等方面的技术,大多数编程语言都会使用但更擅长Java、Python、C++。平时喜欢看书、写作、运动,擅长的项目有篮球、跑步、游泳、健身、羽毛球。崇尚开源,崇尚技术自由,更崇尚思想自由。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • seaboat
    栈主

小栈成员

查看更多
  • 小雨滴
  • Tester9456
  • 栈栈
  • dkl187788
戳我,来吐槽~