完全二叉树
完全二叉树（ complete binary tree ）是一种特别的二叉树，它具有以下特性：
- 树的每一层都是完整的，只有最后一层可能例外；
- 就算最后一层不完整，节点也是从左到右依次排列的；
从根节点开始，逐层给每个节点依次编号，我们发现节点编号是有规律的。以编号为 $i$ 的节点为例：
- 它的父节点编号是：$\frac{i-1}{2}$
- 它的左子节点编号是：$i \times 2 + 1$
- 它的右子节点编号是：$(i + 1) \times 2$
因此，我们可以用数组来保存完全二叉树。根据某个节点在数组中的下标，我们可以通过公式计算其父节点和子节点的下标。这样就不用额外保存子节点指针，可以节约很多内存，存储效率极高。
堆
如果完全二叉树父节点的值，总是小于等于（或大于等于）子节点，那么它就称为 堆 （ heap ）。
- 如果父节点总是 小于等于 子节点，那么称为 最小堆（ min heap ），又可称为 小顶堆 ；
- 如果父节点总是 大于等于 子节点，那么称为 最大堆 （ max heap ），又可称为 大顶堆 ；
堆的性质决定了其最小值（或最大值）一定在 堆顶（根节点），可以应用到很多场景，例如：
我们最好保证堆是一棵完全二叉树，这样做有两个好处：
- 完全二叉树形态是固定的，因此可以用数组来保存，效率极高；
- 完全二叉树高度最低，因此操作效率也很高（插入弹出等操作的效率跟树的高度线性相关）；
构建堆（逐个插入法）
既然堆这么有用，我们如何构建一个堆呢？最简单的做法是构建一个空堆，然后将数据逐一插进去。
假设 push_heap 函数负责将一个新元素插入堆，那么建堆函数 build_heap 可以这样写：
插入新元素
那么，现在问题就变成——如何将一个新元素插入一个已有的堆？
- 将新元素插到堆的尾部（作为最后一个叶子节点）；
- 再视情况上浮新节点，使其满足堆的性质（向上整理）；
push_heap 函数先将新元素追加到数组尾部，再调用 shift_heap_item_up 执行向上整理：
shift_heap_item_up 函数比较新元素跟父节点的大小，新元素更大则交换位置，直到根节点。如此一来，新元素每次不断循环上浮，最终到达正确位置。
弹出堆顶
堆的性质决定了 堆顶（根节点）就是最大值或最小值，因此将堆顶元素从堆中弹出是一个很有用的操作。举个例子，堆可以用来实现优先任务队列，弹出堆顶即可取出优先级最高的任务。
那么，如何将堆顶元素从堆中弹出呢？
- 将堆顶元素取出；
- 将最后一个叶子节点挪到堆顶；
- 重新调整根节点，使它满足堆的性质（向下整理）；
注意到，我们之所以用最后一个叶子节点来填补根节点的空缺，就是为了保证堆是完全二叉树。如果我们是拿它的最大子节点来填补，最终堆的形态很可能就不是完全二叉树了。
构建堆（两两合并）
温馨提示：向下整理的步骤请参考弹出堆顶部分，这里两个场景本质是一样的：对不满足堆性质的根节点进行调整，使得树重新满足堆的性质。
堆排序
掌握堆的性质后，我们知道可以利用它来排序数据：
- 将待排序数据构建成一个堆；
- 循环弹出堆顶（最大值或最小值），直到堆为空；
- 堆顶元素组成的序列就是有序序列；
- 如果构建的堆是最小堆，弹出的序列是 升序 的（从大到小排列）；
- 如果构建的堆是最大堆，弹出的序列是 降序 的（从小到大排列）；
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
小菜学编程
