堆

堆也是一种树形结构，对于树结构，通常从二叉树开始探索，所以这篇文章讲一讲二叉堆。

二叉堆本身就是一个二叉树，只不过其满足了一个严格的条件：任何一个父节点，都比其左右子节点大（或者都比其子节点小），这样就对应存在大根堆和小根堆。

大根堆：根节点的值是整棵数里面值最大的节点，同理，小根堆中的根节点是整棵树中值最小的节点。

来两张图对比一下大根堆和小根堆的差别。

image image

这里，强调的是父节点与子节点的关系，并不在乎子节点之间的关系。

对于堆来说，有两个最主要的操作：上浮、下沉。向一个堆增加一个节点或者删除一个节点，如何保证增加或者删除之后，其依旧满足堆的性质？答案就是通过上浮和下沉操作维持其特性。下面我们以上图中的小根堆举例子。

arr = {null,5,10,15,20,17,16,30}

定义一个数组（伪代码），把数组下标0的位置空出来，得到对应的二叉堆如下图。

数组小根堆.png

这里数组空出来第一个位置是为了方便求给定一个节点，求它的父节点或者左右子节点的下标。例如元素10的下标是2，他的左孩子在数组中对应的下标为2 * 2，右孩子下标为2 * 2+1。

上浮：往数组末尾添加一个元素1。

arr = {null,5,10,15,20,17,16,30,1}

二叉堆为下图所示：

小根堆添加1.png

现在这个数组对应的二叉堆显然不满足堆的性质。开始上浮操作：获取下标8对应的父节点下标4，发现20比1大，两个元素交换位置。

交换.png

同理交换下标4和下标2的元素。

交换.png

再交换下标2和下标1的元素。

交换.png

此时元素1最小，通过上浮操作达到堆顶，并且对于每个节点，都满足小根堆的性质。

接下来讲一讲下沉操作，在堆排序算法中，把对顶元素取走之后，对剩下的元素再次进行构建堆的操作，在这里我们就可以使用下沉操作将剩余节点构建成堆。

比如，把元素1取走，此时作为根节点的元素我们使用最后一个元素进行替换。变成下图。

下沉.png

此时的堆，不满足要求。对于元素20，我们期望它回到自己对应的位置，对顶元素也一定是所有元素中最小的。具体操作：拿20和5、15两个元素比较，与较小者互换。

下沉.png

此时对于元素20，其所在位置也不满足小根堆的性质。再次进行下沉，与元素10互换。

下沉.png

这时的堆，满足要求。
关于堆这个数据结构，本篇文章就分享到这里，有疑问的小伙伴欢迎留言和我讨论。代码实现就不在文章分享里，理解了原理，我相信代码编写一定没有难度。