摘要
堆可以分为大顶堆和小顶堆，是根据节点与子节点的比较来界定。文章中可以使用数组来存放元素，并处理节点与子节点的比较和交换，就是利用了二叉树的基础性质，看完文章相当于再次温习了二叉树的基础性质。
堆可以分为大顶堆和小顶堆，大顶堆的定义就是每个节点的值都大于或等于其左右子节点的值。小顶堆和大顶堆相反，即每个节点的值都小于或等于其左右子节点的值。接下来的说明以大顶堆为例。
根据大顶堆的定义可以梳理出这几点特性：
- 根节点的值是最大的
- 节点的左右子节点没有左子节点值必须小于右子节点值，反之也是没有限制
- 节点、它的左子节点、它的右子节点这三个节点中，节点的值是最大的
接下来，咱就用数组来实现大顶堆的数据结构。为什么要用数组而不是二叉树来实现？带着问题，继续往下看，后面给出答案。
首先创建一个大顶堆的类结构，并定义数组、数量等属性
public class BinaryHeap<E> {
private E[] elements;
private int size;
}假设将 elements 数组里 index 索引中的元素放到合适的位置，这时就要考虑两点：
- index 索引位置在叶子节点
- index 索引位置在非叶子节点
如果是情况1，那就可以不做处理，因为依据特性2来看，子节点之间没有比较元素的要求，凡是叶子节点，都是子节点，所以叶子节点可以不用处理，等着它的父节点来主动比较。
如果是情况2，那么就需要和它的左右子节点比较，然后和最大值的节点交换，在编写逻辑之前，首先要确定以下几点（假定节点的索引为 index，数组中元素的数量为 size）：
- 非叶子节点的数量 half = size >> 1（half = size / 1）；
- 节点的左子节点索引 leftIndex = (index << 1) + 1；
- 节点的右子节点索引 rightIndex = leftIndex + 1；
位运算符示例：
x << 1: x *2
x >> 1: x / 2
上面这 3 点都是二叉树的基本特性，可以看第六期再温习一下，下面就可以编写防治 index 索引的节点的代码：
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1; // 取出非叶子节点
// 第一个叶子结点的索引 == 非叶子节点的数量
// 必须保证 index 是非叶子节点
while (index < half) {
// index 的节点有2种情况
// 1、只有左子节点
// 2、同时有左右子节点
// 默认左子节点跟它进行比较
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子节点
int rightIndex = childIndex + 1;
// 保证右子节点存在（rightIndex < size），并比较左右子节点
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
child = elements[ childIndex = rightIndex];
}
if (compare(child, element) < 0) break;
// 将子节点存放到index位置
elements[index] = child;
// 重新设置 index，继续判断
index = childIndex;
}
elements[index] = element;
}看 siftDown 方法的实现逻辑，可以发现是从 index 往下过滤，寻找合适的位置，那么有没有从 index 往上过滤呢？上代码：
private void siftUp(int index) {
E e = elements[index];
while (index > 0) {
// 得到 index 位置节点的父节点
int pIndex = (index - 1) >> 1;
E p = elements[pIndex];
// 节点小于或等于它的父节点时，结束
if (compare(e, p) <= 0) break;
// 交换节点元素，父节点设置为 index 节点再进行判断
elements[index] = p;
index = pIndex;
}
elements[index] = e;
}(index - 1) >> 1 就是获取父节点索引代码，也是二叉树的基本性质。
当解决将 index 索引节点放在合适位置的核心问题之后，就可以处理后面这几个需求了。
比如，当需要批量添加元素，即直接将一个数组处理成大顶堆时（假设元素已经放入 elements 中 ）：
// 批量建堆
private void heapify() {
// 自下而上的下滤，只需要处理非叶子节点即可
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}如果使用 siftUp 函数来实现批量建堆，就需要从头遍历到最后的位置：
// 批量建堆
private void heapify() {
// 自上而下的上滤
for (int i = 0; i < size; i++) {
siftUp(i);
}
}总结：
- 大顶堆就是每个节点都大于它的左右子节点，小顶堆刚相反；
- 非叶子节点的数量 half = size >> 1（half = size / 1）；
- siftDown 来批量建堆时，可以减少一半的遍历次数；