数据结构之二叉堆(Java)

一：概述

二叉堆：二叉堆本质上是一种完全二叉树，它分为两个类型。

• 最大堆
• 最小堆

二：最大堆与最小堆的具体说明

<1>最大堆

最大堆的任何一个父节点的值，值大于或等同于它左、右孩子节点的值。例子如下图所示：

<2>最小堆

最小堆的任何一个父节点的值，都小于或等于它的左、右孩子节点的值。例子如下图所示：

二叉堆的根节点叫做堆顶。

最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中最小的元素。

三：二叉堆的自我调整

二叉堆有以下的几种操作。

• 插入节点
• 删除节点
• 构建二叉堆

这几种操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整成一个堆。下面以最小堆为例子，来看看二叉堆是如何进行自我调整的。

<1>插入节点

当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。例如插入一个新的节点，值为0.

这时，新节点的父节点5比0大，这不符合最小二叉堆的性质。所以让新节点“上浮”，和父节点交换位置。

继续用节点0和父节点3做比较，因为0小于3，则让新节点继续“上浮”。

继续比较，最终节点0“上浮”到了堆顶的位置。

<2>删除节点

二叉堆删除节点和插入节点的过程正好相反，所以删除的是处于堆顶的节点。例如删除最小堆的堆顶点1.

为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临时补到原本堆顶的位置。

接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果左、右孩子节点种最小的一个(显然是节点2)比节点10小，那么让节点10“下沉”。

继续让节点10和它的左、右孩子做比较，左、右孩子种最小的是节点7，由于10大于7，让节点10继续“下沉”。

二叉堆得到了重新的调整。

<3>构建二叉堆

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点依次“下沉”。

下面是一个无序完全二叉树的例子，如下图所示。

首先，从最后的一个非叶子点开始，也就是从节点10开始。如果节点10大于它的左、右孩子节点中最小的一个，则节点10“下沉”。

接下来是节点3，如果节点3大于它的左、右孩子节点中最小的一个，则节点3“下沉”。

然后是节点1，如果节点1大于它的左、右孩子节点中最小的一个，则节点1“下沉”。在这个例子中，节点1是小于它的左、右孩子节点的，所以不用改变。接下来是节点7，如果节点7大于它的左、右孩子节点中最小的一个，则节点7“下沉”。

节点7继续比较，继续“下沉”。

经过上述几轮比较“下沉”后，最终每一父节点都小于它的左、右孩子节点，一个无序的完全二叉树就被构建成了一个最小堆。

堆的插入操作操作是单一节点的“上浮”，堆的删除操作是单一节点的“下沉”，这两个操作的平均交换次数都是堆高度的一半，所以时间复杂度是O(logn)，至于堆的构建，需要所有非叶子点依次“下沉”，所以时间复杂度你可能想的是O(logn)，但是构建堆的时间复杂度不是O(nlogn)，而是O(n)。这里涉及数学推导，有兴趣的可以想一下。

四：二叉堆的代码实现

在写代码之前，还需要明确：二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组中。

在数组中，在没有左、右指针的情况下，如何定位一个父节点的左孩子和右孩子呢？

根据向上图这样，可以依靠数组下标来计算。

假设父节点的下标是parent，那么它的左孩子下标就是 2 x parent + 1；右孩子下标就是2 x parent + 2。

假设上面的例子中，节点4包含节点9和节点10两个孩子节点，节点4在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8.

那么：

7 = 3 x 2 + 1

8 = 3 x 2 + 2

发现刚好符合规律。有了这个前提，代码能好理解一点。

package com.algorithm2;


import java.util.Arrays;

/**
 * 二叉堆
 */
public class BinaryHeap {

    /**
     * "上浮"调整
     * @param array  待调整的堆
     */


    public static void upAdjust(int[] array) {
        // 定义孩子索引
        int childIndex = array.length - 1;
        // 定义父亲节点索引
        int parentIndex = (childIndex - 1) / 2;
        // temp保存在插入叶子节点的值，用于最后的赋值
        int temp = array[childIndex];
        // 当孩子索引大于0，并且临时保存插入叶子节点的值小于父亲节点的值时
        while (childIndex > 0 && temp < array[parentIndex])
        {
        // 无须真正交换，单向赋值即可
        array[childIndex] = array[parentIndex];
        // 孩子索引等于父亲节点索引
        childIndex = parentIndex;
        // 父亲节点索引等于（父亲节点索引 - 1 ）的一半
        parentIndex = (parentIndex - 1) / 2;
        }
        // 将temp赋值给孩子节点对应索引的值
        array[childIndex] = temp;
    }

    /**
     * “下沉”调整
     * @param array 待调整的堆
     * @param parentIndex  要“下沉”的父节点
     * @param length 堆的有效大小
     */

     public static void downAdjust(int[] array, int parentIndex,int length) {
        // temp保存父节点的值，用于最后的赋值
         int temp = array[parentIndex];
        // 令孩子节点索引等于父亲节点索引的2倍 + 1
         int childIndex = parentIndex * 2 + 1;
         while (childIndex < length) {
             // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
             if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                 childIndex++;
             }
             // 如果父节点小于任何一个孩子节点的值，则直接跳出
             if (temp <= array[childIndex])
                 break;
             // 无须真正交换，单向赋值即可
             array[parentIndex] = array[childIndex];
             parentIndex = childIndex;
             childIndex = 2 * childIndex + 1;
             array[parentIndex] = temp;
         }
     }

    /**
     * 构建堆
     * @param array 待调整的堆
     */

     public static void buildHeap(int[] array) {
         // 从最后一个非叶子点开始，依次做“下沉"调整
         for (int i = (array.length - 2) / 2; i >= 0; i--) {
             downAdjust(array, i, array.length);
         }
     }


  public static void main(String[] args) {
         int[] array = new int[] {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
         upAdjust(array);
         System.out.println(Arrays.toString(array));

         array = new int[] {7, 1, 3 ,10, 5, 2, 8, 9, 6};
         buildHeap(array);
         System.out.print(Arrays.toString(array));
  }

}

在这里代码有一个需要优化的点，就是在父节点和孩子节点做连续交换时，并不一定要真的交换

只需要先把交换的一方的值存入temp变量，最单向覆盖，循环结束之后，再把temp的值存入

交换后的最终位置即可。