这是【字节可视化系列】堆排序的第一篇文章。同时，文末会放上一张【速记卡】，方便快速回顾本文关键知识点。

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

提到堆，其实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制作而成。