二叉堆本质上是一种完全二叉树，分为两个类型：
- 最大堆
- 最小堆
最大堆
每个父节点的值都大于等于子节点的值。
最大堆.png
最小堆
每个父节点的值都小于等于子节点的值。
最小堆.png
特点：
二叉堆的根节点叫做堆顶
最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。
堆的自我调整
对于二叉堆来说，自我调整的操作有以下三个：
- 插入节点
- 删除节点
- 构建二叉堆
1. 插入节点
二叉堆节点的插入，插入的位置是二叉树的最后一个位置。
举个例子：给一个最小堆插入一个新节点，值为0。0.png
这时候，把插入的新节点，与它的父节点9进行比较。如果比9小，则让新节点上浮，和父节点交换位置。1.png
继续把新节点0与父节点5进行比较，如果小于父节点，继续上浮。
2.png
继续比较，最终新节点0上浮到了堆顶的位置。
3.png
最大堆的插入，和最小堆同理。区别在于最大堆是新节点如果比父节点大，则新节点上浮。
2. 删除节点
二叉堆节点的删除，与插入过程正好相反。删除的是处于堆顶的节点。
举个例子：删除一个最小堆的堆顶节点0。
00.png
这时候，为了维持二叉树的结构，把堆的最后一个节点9，补到堆顶的位置。
11.png
接下来，把移到堆顶的9，与它的左右子节点进行比较。如果左右子节点中最小的一个比堆顶节点9小，那么让节点9下沉，与子节点交换位置。
22.png
然后节点9继续与左右子节点进行比较，然后交换位置。
33.png
这样，二叉堆就重新得到了调整。
3. 构建二叉堆
构建二叉堆，实际上就是把一个无序的完全二叉树调整为二叉堆，就是让所有的非叶子节点依次下沉。
4. 堆的代码实现方法
二叉堆虽然是一个完全二叉树，但储存方式是顺序存储，而不是链式存储。实际上二叉堆的所有节点都存储在数组里面。
因此，在数组里面我们可以依靠数组的下标来计算子节点位置。
假设父节点下标是x，那么它的左边子节点的下标就是 2*x+1。右边子节点下标是2*x+2。
Talk is cheap , show me the code.
/**
* 上浮调整
*/
private static void upAdjust(int[] array) {
int arrLength = array.length;
int childIndex = arrLength - 1;
// 子节点的下标是 2*x+1 ,反推父节点下标
int parentIndex = (childIndex - 1) / 2;
// temp 保存子节点的值
int temp = array[childIndex];
while (childIndex > 0 && temp < array[parentIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
array[childIndex] = temp;
}
/**
* 下沉调整
*/
private static void downAdjust(int[] array, int parentIndex) {
int arrLength = array.length;
// 左子节点下标
int childIndex = 2 * parentIndex + 1;
int temp = array[parentIndex];
while (childIndex < arrLength) {
// 如果有右节点，且右节点小于左节点
if (childIndex + 1 < arrLength && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
// 如果父节点小于两个子节点
if (temp < array[childIndex])
break;
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
/**
* 构建堆
*/
private static void buildHeap(int[] array) {
int arrLength = array.length;
// 从最后一个非叶子节点开始下沉
for (int i = arrLength / 2; i >= 0; i--) {
downAdjust(array, i);
}
}
