堆的概念：

堆是具有以下性质的完全二叉树：

  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
  • 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系
一般升序采用大顶堆，降序采用小顶堆

示例说明：

1)大顶堆举例说明

image.png
我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子:
image.png
大顶堆特点：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点，i从0开始编号

2)小顶堆举例说明

image.png
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点，i从0开始编号

二叉堆的操作

对于二叉堆， 有如下几种操作。
1. 插入节点。
2. 删除节点。
3. 构建二叉堆。
这几种操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树， 调整成一个堆。下面让我们以最小堆为例，看一看二叉堆是如何进行自我调整的。

1. 插入节点

当二叉堆插入节点时， 插入位置是完全二叉树的最后一个位置。 例如插入一个新节点， 值是 0。
image.png
这时， 新节点的父节点5比0大， 显然不符合最小堆的性质。 于是让新节点“上浮”， 和父节点交换位置。
image.png
继续用节点0和父节点3做比较， 因为0小于3， 则让新节点继续“上浮”。

image.png
继续比较， 最终新节点0“上浮”到了堆顶位置
image.png

2. 删除节点

二叉堆删除节点的过程和插入节点的过程正好相反， 所删除的是处于堆顶的节点。 例如删除最小堆的堆顶节点1。
image.png
这时， 为了继续维持完全二叉树的结构， 我们把堆的最后一个节点10临时补到原本堆顶的位置。
image.png
接下来， 让暂处堆顶位置的节点10和它的左、 右孩子进行比较， 如果左、 右孩子节点中最小的一个（显然是节点2） 比节点10小， 那么让节点10“下沉”。
image.png
继续让节点10和它的左、 右孩子做比较， 左、 右孩子中最小的是节点7， 由于10大于7， 让节点10继续“下沉”。
image.png
这样一来， 二叉堆重新得到了调整。

3. 构建二叉堆

构建二叉堆， 也就是把一个无序的完全二叉树调整为二叉堆， 本质就是让所有非叶子节点依次“下沉” 。
下面举一个无序完全二叉树的例子， 如下图所示。
image.png
首先， 从最后一个非叶子节点开始， 也就是从节点10开始。 如果节点10大于它左、 右孩子节点中最小的一个， 则节点10“下沉”。
image.png
接下来轮到节点3， 如果节点3大于它左、 右孩子节点中最小的一个， 则节点3“下沉”。
image.png
然后轮到节点1， 如果节点1大于它左、 右孩子节点中最小的一个，则节点1“下沉”。 事实上节点1小于它的左、 右孩子， 所以不用改变。
接下来轮到节点7， 如果节点7大于它左、 右孩子节点中最小的一个， 则节点7“下沉”。
image.png
节点7继续比较， 继续“下沉”。
image.png
经过上述几轮比较和“下沉”操作， 最终每一节点都小于它的左、 右孩子节点， 一个无序的完全二叉树就被构建成了一个最小堆。

二叉堆的代码实现

在展示代码之前， 我们还需要明确一点： 二叉堆虽然是一个完全二叉树， 但它的存储方式并不是链式存储， 而是顺序存储。 换句话说， 二叉堆的所有节点都存储在数组中。
image.png
在数组中， 在没有左、 右指针的情况下， 如何定位一个父节点的左孩子和右孩子呢？
像上图那样， 可以依靠数组下标来计算。
假设父节点的下标是parent， 那么它的左孩子下标就是2×parent+1； 右孩子下标就是2×parent+2。
例如上面的例子中， 节点6包含9和10两个孩子节点， 节点6在数组中的下标是3， 节点9在数组中的下标是7， 节点10在数组中的下标是8。 则：
7 = 3×2+1
8 = 3×2+2
刚好符合规律。
有了这个前提， 编写代码如下：

  1. import java.util.Arrays;
  2. public class Heap {
  3.     /**
  4.      * 使用“下沉”调整构建小顶堆
  5.      * @param array       待调整的堆
  6.      * @param parentIndex 要“下沉”的父节点
  7.      * @param length      堆的有效大小
  8.      */
  9.     public static void downAdjustMin(int[] array, int parentIndex, int length) {
  10.         // temp 保存父节点值， 用于最后的赋值
  11.         int temp = array[parentIndex];
  12.         // childIndex先定位到左孩子
  13.         int childIndex = 2 * parentIndex + 1;
  14.         while (childIndex < length) {
  15.             // 如果有右孩子， 且右孩子小于左孩子的值， 则定位到右孩子
  16.             if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
  17.                 childIndex++;
  18.             }
  19.             // 如果父节点小于任何一个孩子的值， 则直接跳出
  20.             if (temp <= array[childIndex]) {
  21.                 break;
  22.             }
  23.             // 无须真正交换， 单向赋值即可
  24.             array[parentIndex] = array[childIndex];
  25.             // 这里也只交换索引即可
  26.             parentIndex = childIndex;
  27.             // 下一次循环childIndex仍然先定位到左孩子
  28.             childIndex = 2 * childIndex + 1;
  29.         }
  30.         array[parentIndex] = temp;
  31.     }
  33.     //使用“下沉”调整构建大顶堆
  34.     public static void downAdjustMax(int[] array, int parentIndex, int length) {
  35.         int temp = array[parentIndex];
  36.         int childIndex = 2 * parentIndex + 1;
  37.         while (childIndex < length) {
  38.             // 这里修改为 >
  39.             if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
  40.                 childIndex++;
  41.             }
  42.             // 这里修改为 >=
  43.             if (temp >= array[childIndex]) {
  44.                 break;
  45.             }
  46.             array[parentIndex] = array[childIndex];
  47.             parentIndex = childIndex;
  48.             childIndex = 2 * childIndex + 1;
  49.         }
  50.         array[parentIndex] = temp;
  51.     }
  53.     //构建小顶堆
  54.     public static void buildHeapMin(int[] array) {
  55.         // 从最后一个非叶子节点开始，依次做“下沉”调整
  56.         // 因为是完全二叉树，所以最后一个非叶子节点之后的节点都是非叶子节点
  57.         // 最后一个非叶子节点为：n/2-1 或 (n-2)/2
  58.         for (int i = (array.length - 2) / 2; i >= 0; i--) {
  59.             downAdjustMin(array, i, array.length);
  60.         }
  61.     }
  62.     //构建大顶堆
  63.     public static void buildHeapMax(int[] array) {
  64.         for (int i = (array.length - 2) / 2; i >= 0; i--) {
  65.             downAdjustMax(array, i, array.length);
  66.         }
  67.     }
  69.     public static void main(String[] args) {
  70.         int[] array = new int[] { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
  71.         //构建小顶堆
  72.         buildHeapMin(array);
  73.         System.out.println(Arrays.toString(array));
  74.         //构建大顶堆
  75.         buildHeapMax(array);
  76.         System.out.println(Arrays.toString(array));
  77.     }
  78. }

代码中有一个优化的点， 就是在父节点和孩子节点做连续交换时，并不一定要真的交换， 只需要先把交换一方的值存入temp变量， 做单向覆盖， 循环结束后， 再把temp的值存入交换后的最终位置即可。