这是【字节可视化系列】堆排序的第一篇文章。同时，文末会放上一张【速记卡】，方便快速回顾本文关键知识点。
本篇的主旨是理解二叉堆结构，所以具体实现代码会留到第二篇讲解。
提到堆，其实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制作而成。
