1. 堆 (Heap)
1.1 堆的概念
堆（Heap）是一种特殊的完全二叉树，它满足父节点的值总是不大于或不小于其子节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆满足以下两个性质:
- 堆中某个节点的值总是不大于或不小于其根节点的值
- 堆总是一棵完全二叉树
1.2 堆的存储方式
从堆的概念可知，堆是一颗完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。
对于非完全二叉树，则不适合使用顺序的方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，这会导致空间利用率比较低。
将元素存储到数组中后，假设 i 为节点在数组中的下标，则有:
- 如果 i 为 0，则 i 表示的节点为根节点，否则 i 节点的双亲节点为 (i - 1)/2
- 如果 2 * i + 1 小于节点个数，则节点 i 的左孩子下标为 2 * i + 1，否则没有左孩子
- 如果 2 * i + 2 小于节点个数，则节点 i 的右孩子下标为 2 * i + 2，否则没有右孩子
1.3 堆的创建
想要创建堆，我们首先要了解向下调整（这里以创建小根堆为例）:
- 我们将想要调整的节点标记为 parent，child 为该节点的左孩子（如果有孩子节点，则一定是现有左孩子）
- 如果有左孩子节点，则判断 child < size（数组元素个数），然后进行以下操作，直到 child < size 条件不成立 2.1 判断 parent 的右孩子是否存在，找到左右孩子中最小的那个，用 child 标记。（如果右孩子比左孩子小，child += 1） 2.2 将 parent 与 child 比较，如果 parent < child，则调整结束；否则进行元素交换，交换完之后，有可能新构建的子树又不满足小根堆，所以需要将 parent = child，child = parent * 2 + 1。然后继续重复 2 操作。这便是向下调整。
public void siftDown(int[] arr, int parent) {
// 此时 child 标记的左孩子，因为 parent 右孩子结点的话只能先有左孩子
int child = parent * 2 + 1;
int size = arr.length;
(child < size) {
(child + < size && arr[child] > arr[child + ]) {
child += ;
}
(arr[parent] <= arr[child]) {
;
} {
arr[parent];
arr[parent] = arr[child];
arr[child] = t;
parent = child;
child = parent * + ;
}
}
}
