阅读 2730

看图轻松理解最小(大)堆

前言

推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。

最小(大)堆

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

image

最小(大)堆性质

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

最小(大)堆作用

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

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

插入操作

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

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

image

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

image

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

image

于是将它们对调。

image

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

image

于是将它们对调。

image

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

image

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

image

于是将它们对调,

image

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

image

继续将它们对调。

image

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

image

于是将它们对调,

image

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

image

继续将它们对调。

image

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

image

于是将它们对调,

image

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

image

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

image

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

image

删除操作

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

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

image

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

image

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

image

1小于8,于是对调。

image

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

image

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

image

2小于8,于是对调。

image

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

-------------推荐阅读------------

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇


跟我交流,向我提问:

欢迎关注:

关注下面的标签,发现更多相似文章
评论