二叉堆
二叉堆是一种特殊的堆，其实质是完全二叉树。二叉堆有两种：最大堆和最小堆。最大堆是指父节点键值总是大于或等于任何一个子节点的键值。而最小堆恰恰相反，指的是父节点键值总是小于任何一个子节点的键值。如“图1 最大堆”、“图2 最小堆”所示：
堆(heap)，这里所说的堆是数据结构中的堆，而不是内存模型中的堆。常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。
数据存储
与二叉树不同的是二叉堆的数据是顺序存储，而不是链式存储。如“图3 二叉堆数据的存储方式”所示：
操作
对于二叉堆，介绍以下几种操作：
插入节点；
上浮节点；
删除节点；
下沉节点；
构建二叉堆；
1.插入节点
在插入数据的时候，每插入的数据都是插入到二叉堆的最后一个位置，以最大堆为例，如“图4 插入数据”所示：
上图描述的是插入整数10，可以发现，在第二层的父节点5小于新插入的子节点10，这可怎么办？这不符合最大堆的性质呀！于是就有了上浮节点操作。
2.上浮节点
插入新数据后（子节点10），我们让子节点10与其父节点5作比较，父节点小于子节点，于是将子节点上浮与父节点转换，如“图5 子节点上浮-01”所示：
接着再做同样的操作，子节点10与父节点8作比较，同样需要上浮，如“图6 子节点上浮-02”所示：
再同样做同样操作，如“图7 子节点上浮-03”所示，直至父节点大于子节点或者子节点已经上浮到根节点即止。
3.删除节点
在删除节点的时候，每次都是删除根节点，如“图8 删除节点”所示：
在删除根节点之后，我们不可能让根节点位置无主吧？于是将二叉堆最后一个数据填充至根节点，如“图9 填充根节点”所示：
但是，我们又可以发现，填充上来的根节点比它的子节点小，这也不符合最大堆的性质呀！于是就有了下沉节点操作。
4.下沉节点
填充数据（父节点5）之后，我们让父节点5与其两个子节点9、7作比较，看谁更大，父节点就往哪下沉，如“图10 下沉父节点-01”所示：
接着再做同样的操作，父节点5与其两个子节点6、8作比较，再下沉。最终发现两个子节点都小于父节点，于是停止下沉（如果父节点下沉至叶节点位置时，也停止下沉）。如“图10 下沉父节点-02”所示：
5.构建 二叉堆
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。
比如此时有一个无序的二叉树，如“图11 无序二叉树”所示：
首先从最后一个非叶子结点8开始，让其与两个子节点11、6作比较，然后做下沉节点操作，如“图12 节点下沉-01”所示：
接着是节点2，做同样的操作，如“图13 节点下沉-02”所示：
然后是节点5，如“图14 节点下沉-03”所示：
最后是节点12，因为该节点都比其两个子节点大，所以无需下沉。
最终，一颗无序的二叉树就构建成了一个最大堆了，如“图15 构建后的最大堆”所示：
时间复杂度
因为二叉堆是一棵完全二叉树，所以对于一个节点数为n的堆，它的高度不会超过log2n，因此二叉堆上浮和下沉的时间复杂度都为log2(n)。
代码实现
在代码实现之前，先说明一下二叉堆在处理的过程中是如何计算下标的，如“图16 下标获取”所示：
如上图所示，假设父节点的下标 parent=0，则其左子节点下标为Lchildren=2*parent+1，右子节点下标为Rchildren=2*parent+2，如上示为例：
第 0 个数据的下标：parent = 0
第 1 个数据的下标：Lchildren = 2*parent + 1 = 2*0+1 = 1
第 2 个数据的下标：Rchildren = 2*parent + 2 = 2*0+2 = 2
代码
package Queue;
import java.util.Arrays;
public class BinaryHeap {
/**
* 上浮
* @param array 数据数组
*/
public static void upAdjust(int[] array) {
// 先求出父子节点的下标
int childrenIndex = array.length - 1;
int parentIndex = (childrenIndex - 1) / 2;
// 记录子节点数据，用于最后赋值
int temp = array[childrenIndex];
// 开始上浮
while (childrenIndex > 0 && temp > array[parentIndex]) {
// 直接单向赋值，无需做交换操作
array[childrenIndex] = array[parentIndex];
// 更新父子节点下标的值，下面两句代码顺序不可相反
childrenIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
// 最后赋值
array[childrenIndex] = temp;
}
/**
* 下沉节点
* @param index 要下浮的节点的下标
* @param array 数据数组
*/
public static void downAdjust(int index, int[] array) {
// 先记录父节点及左子节点的下标
int parentIndex = index;
int childrenIndex = 2 * parentIndex + 1;
// 记录父节点的值，用于最后赋值
int temp = array[parentIndex];
// 若有左子节点则继续
while (childrenIndex <= array.length - 1) {
// 若有右子节点，且右子节点比左子节点大，则将 childrenIndex 记录为右子节点的下标
if (childrenIndex + 1 <= array.length - 1 && array[childrenIndex + 1] > array[childrenIndex]) {
childrenIndex++;
}
// 如果子节点大于父节点，则无需下沉，直接返回
if (temp >= array[childrenIndex]) {
break;
}
// 直接单向赋值，无需做交替操作
array[parentIndex] = array[childrenIndex];
// 更新父子节点下标的值，下面两句代码顺序不可相反
parentIndex = childrenIndex;
childrenIndex = 2 * childrenIndex + 1;
}
// 最后赋值
array[parentIndex] = temp;
}
/**
* 构建二叉堆
* @param array 数据数组
*/
public static void buildBinaryHeap(int[] array) {
for (int i = (array.length/2)-1; i >= 0; i--) {
downAdjust(i, array);
}
}
public static void main(String[] args) {
// 构建二叉堆
int[] arr01 = {5, 3, 6, 9, 8, 6, 7, 2, 4, 6, 3};
buildBinaryHeap(arr01);
System.out.println(Arrays.toString(arr01));
// 添加一个数据，测试上浮操作
int[] arr02 = {9, 8, 7, 4, 6, 6, 6, 2, 3, 5, 3, 20};
upAdjust(arr02);
System.out.println(Arrays.toString(arr02));
// 删除一个数据，册数下沉操作
int[] arr03 = {3, 8, 7, 4, 6, 6, 6, 2, 3, 5};
downAdjust(0, arr03);
System.out.println(Arrays.toString(arr03));
}
}
总结
1.二叉堆的核心代码是上述的upAdjust()、downAdjust()函数，在实现时要注意 while 循环条件判断时是判断childrenIndex以及在更新父子节点下标的值顺序不可倒置；
2.二叉堆是优先队列的理论基石。理解了二叉堆之后，优先队列就很简单了。
