下载掌阅APP，畅读海量书库
立即打开
前面讲优先队列的时候提到过堆，因为优先队列可以通过堆来实现，也可以把堆看作是一棵完全二叉树。堆一般分为两种，一种是最大堆（有的也叫作大根堆、大顶堆），另一种是最小堆。最大堆根节点的值是堆中最大的，最小堆根节点的值是堆中最小的。两者原理差不多，这里只介绍其中一种，我们就拿最小堆来讲解。因为堆是一棵完全二叉树，所以如果知道子节点的下标，那么一定知道父节点的下标；如果知道父节点的下标，也一定知道子节点的下标（假设有子节点），如图1-59所示。
•图1-59
它们的关系如下：
堆的常见操作有两种，一种是往堆中添加元素，另一种是删除堆顶元素。往堆中添加元素实际上相当于在完全二叉树中添加一个叶子节点，添加完之后还需要往上调整，就是和父节点比较谁的值小（这里介绍的是最小堆），如果比父节点小，就和父节点交换，交换完之后，还要继续往上比较，如果比父节点值大，就不再交换，如图1-60所示。
•图1-60
这样通过不断和父节点比较，如果添加的元素是堆中最小的，它就会跑到根节点，也就是最小堆的根节点是堆中所有元素中最小的。如果添加元素不比父节点小，就不需要交换。
堆中元素的添加只需要和父节点比较即可，因为一个节点最多只能有一个父节点（根节点没有父节点）。但堆的删除就有点麻烦了，因为如果直接删除，就会把一棵二叉树变成两棵二叉树。实际上堆的删除并不是直接删除，而是让最后一个叶子节点（二叉树最下面一行最右边的节点）替换根节点，然后根节点往下调整，如图1-61所示，往下调整的步骤如下：
（1）如果根节点比它的两个子节点都小，就不需要往下调整。
（2）如果其中的一个子节点比根节点小，那么根节点就和那个比它小的子节点交换，交换完之后继续往下比较。
（3）如果根节点比它的两个子节点都大，那么根节点就和那个最小的子节点交换，交换完之后继续往下比较。
•图1-61
所以堆的添加会涉及往上调整，而堆的删除会涉及往下调整，这里的删除只是删除堆顶元素，如果不是堆顶元素，两个方向都要考虑，我们来看一下代码。
