Java教程

图说堆排序

本文主要是介绍图说堆排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
这是【字节可视化系列】堆排序的第一篇文章。同时，文末会放上一张【速记卡】，方便快速回顾本文关键知识点。

本篇的主旨是理解二叉堆结构，所以具体实现代码会留到第二篇讲解。

提到堆，其实Java中的优先队列PriorityQueue就是基于堆结构实现的；

而Java中的延迟队列DelayQueue里面就用到了PriorityQueue；

再比如kafka中基于时间轮TimingWheel实现的延时定时器, 同样离不开DelayQueue的配合。

这一切都和堆息息相关。


1 数组和树

堆其实就是一个数组结构, 如图


下面我们来点小魔法, 把数组变成树!


这个数组对应的树结构就是下面这样:


数组结构的下标和树结构的节点对应关系如下：

如果根节点对应的数组下标是0, 那么对于 i 节点，

左右子节点的位置为 2i +１和 2i+２；

i 节点的父节点位置为 ( i-1)/2；


简单理解了数组和树之后，下面我们进入正题。



2 最小堆结构

首先我们来一个乱序的数组：


这个数组对应的树结构：


这只是一个简单的树结构, 还不是堆, 堆结构是下面这样子的:


这是一个最小堆, 可以看到根节点, 也就是堆顶, 是数组中最小的那个元素。

同时，整一个大的堆, 是由很多个小的堆组成的。

比如左边这个小堆, 也是符合最小堆的定义, 堆顶的4是三个数字中最小的：


右边的小堆也是一个最小堆, 堆顶的3是最小的数字：


那么怎么把一颗树变成一个最小二叉堆呢?

3 插入和上浮

最简单的办法, 就是新建一个空的堆(一个空的数组), 把乱序数组中的所有元素依次插入到堆中, 在这个过程中堆会通过上浮来调整自身的结构。


下面我们来解析下上面的动画:

首先, 是往堆中 插入 元素, 比如往下面的这个最小堆中插入数字1:


当1插入数组尾部之后, 就处于树的最后一个叶子节点的位置:



然后通过 上浮 操作, 把A移到合适的位置。

简单来说就是先和A的父节点比较, 如果比父节点小, 就和父节点交换位置, 这个过程一直持续到A的父节点比A小, 或者A已经到达堆顶的位置。

下面继续数字1这个例子, 当1插入数组尾部之后, 会和他的父节点8作比较:



1比父节点8小, 交换位置:


1再和他的父节点4作比较:


1比父节点4小, 交换位置后1到达堆顶, 形成了一个最小堆结构。



4 删除和下沉

接下来讲讲堆节点的删除, 这里的删除是指取出堆顶的节点。

我们把堆顶的元素取出后, 堆会把剩下的数字中最小的那个数字再次推到堆顶的位置。


仔细看动画，这里值得注意的是, 取出堆顶的元素, 并不是直接把堆顶的元素删除。什么意思呢?


在JavaScript中, 数组的pop操作就是把数组中最后一个元素删除; 而Java中的堆栈Stack也有pop操作, 同样是把最后一个元素移除。


而堆的 删除 操作, 也是基于pop操作来实现。这样做是为了维持完全二叉树的结构。


比如我们要把堆顶的1删除：

1. 先把根节点和最后一个节点交换位置, 也就是1和6交换位置；


此时堆顶不再是最小的数字，最小堆的特性被打破, 接下来我们要对堆顶的元素进行 下沉 操作, 把树结构重新调整为堆结构。


2. 先比较左右子节点大小，与最小节点交换位置 ;

3. 继续步骤2;


继续上面的例子，当1节点移除后，此时会先对堆顶6的左右子节点进行大小比较， 找出比较小的那个子节点，也就是右节点3：


然后， 节点6再和右节点3比较：


节点6下沉, 此时6已经是叶子节点了, 下沉操作结束, 可以看到此时整棵树已经重新变回了最小堆结构：


5 堆排序

有趣的是, 通过上面简单的【插入并上浮】 和 【删除并下沉】 , 我们就可以对乱序数组执行堆排序了。

下面对乱序数组进行堆排序：


堆化，插入并上浮：


删除并下沉：



排序完成后的数组：


最后对堆排序的总结就是:
1. 先把乱序数组堆化 (文中使用的是插入+上浮)
2. 再通过pop操作删除堆顶元素, 通过下沉调整堆结构


6 堆化 Heapify

平常的使用堆排序肯定不会再新建一个空的堆, 再把乱序数组的元素逐个插入堆中, 这样太浪费空间, 下一章我们来讲一下堆化。


7 色谱图


简单了解了堆排序后, 我们来看看16个元素进行堆排序后生成的色谱图

也有网友说这是大肠图, 感兴趣的可以看看这篇文章了解下【译】排序算法可视化之色谱图， 后面本公众号会开一个系列专门讲解这种有趣的静态可视化方法。


我们把这个图拆成两部分来看, 首先是左边部分

这就是堆排序的第一步, 堆乱序数组堆化的过程

再来看看右边部分


可以看到, 堆排序的第二步就是pop操作把堆顶元素移除, 图中也体现得非常清晰,先把堆顶元素移到尾部, 被移除的元素就相当于排好序了.

每次移除元素后, 都会对新的堆顶节点执行下沉操作, 也就是图中pop和pop之间的红框部分, 我们可以清晰地看到堆在自我调节的过程


排序结束之后, 由浅到深的颜色依次呈现在我们眼前!


温馨提示

文中的动画是基于d3.js制作而成。





这篇关于图说堆排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航