二叉堆

雨点打透心脏的1/2处 2021-12-15 00:47 249阅读 0赞

**什么是二叉堆？**

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

**1.最大堆**

**2.最小堆**

什么是最大堆呢？最大堆任何一个父节点的值，都**大于等于**它左右孩子节点的值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70][]

什么是最小堆呢？最小堆任何一个父节点的值，都**小于等于**它左右孩子节点的值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 1][]

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

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

**如何构建一个堆？**

这个需要二叉堆的自我调整。

**堆的自我调整**

对于二叉堆，如下有几种操作：

**插入节点**

**删除节点**

**构建二叉堆**

这几种操作都是基于堆的自我调整。

下面让我们以最小堆为例，看一看二叉堆是如何进行自我调整的。

**1.插入节点**

二叉堆的节点插入，插入位置是完全二叉树的最后一个位置。比如我们插入一个新节点，值是 0。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 2][]

这时候，我们让节点0的它的父节点5做比较，如果0小于5，则让新节点“上浮”，和父节点交换位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 3][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 4][]

继续比较，最终让新节点0上浮到了堆顶位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 5][]

**2.删除节点**

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 6][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 7][]

接下来我们让移动到堆顶的节点10和它的左右孩子进行比较，如果左右孩子中最小的一个（显然是节点2）比节点10小，那么让节点10“下沉”。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 8][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 9][]

这样一来，二叉堆重新得到了调整。

**3.构建二叉堆**

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

我们举一个无序完全二叉树的例子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 10][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 11][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 12][]

接下来轮到节点1，如果节点1大于它左右孩子中最小的一个，则节点1下沉。事实上节点1小于它的左右孩子，所以不用改变。

接下来轮到节点7，如果节点7大于它左右孩子中最小的一个，则节点7下沉。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 13][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 14][]

这样一来，一颗无序的完全二叉树就构建成了一个最小堆。

**二叉堆的代码实现**

在撸代码之前，我们还需要明确一点：

二叉堆虽然是一颗完全二叉树（二叉树一般是采用**链表**的方式来实现的），但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组当中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 15][]

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

像图中那样，我们可以依靠数组下标来计算。

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

比如上面例子中，节点6包含9和10两个孩子，节点6在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8。

7 = 3\*2+1

8 = 3\*2+2

刚好符合规律。

有了这个前提，下面的代码就更好理解了：

/**
         * 上浮调整
         * @param array     待调整的堆
         */
        public static void upAdjust(int[] array) {
            int childIndex = array.length - 1;
            int parentIndex = (childIndex - 1) / 2;
            int temp = array[childIndex];/* temp保存插入的叶子节点值，用于最后的赋值*/
            while (childIndex > 0 && temp < array[parentIndex]) {/*无需真正交换，单向赋值即可*/
                array[childIndex] = array[parentIndex];
                childIndex = parentIndex;
                parentIndex = (parentIndex - 1) / 2;
            }
            array[childIndex] = temp;
        }
    
        /**
         * 下沉调整
         *
         * @param array       待调整的堆
         * @param parentIndex 要下沉的父节点
         * @param parentIndex 堆的有效大小
         */
        public static void downAdjust(int[] array, int parentIndex, int length) {/* temp保存父节点值，用于最后的赋值*/
            int temp = array[parentIndex];
            int childIndex = 2 * parentIndex + 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);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70]: /images/20211214/120ebf47f1c24fd5afee9197ead83218.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 1]: /images/20211214/fc2180db9f0841c9a6f9a8c8dc7ef09b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 2]: /images/20211214/5d5cfd10ff73455bb1821ebe45a82996.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 3]: /images/20211214/ddf4a4dfa0a946bfa068e0dd98d75850.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 4]: /images/20211214/b11580e4d8444b4abf18363af193e114.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 5]: /images/20211214/165d8bfc07fd43999b795ae88ef1cd80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 6]: /images/20211214/fd6622b0086f49799849c3baee2516a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 7]: /images/20211214/48854b47b6444bea92dd1b57da72045a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 8]: /images/20211214/a2e9da26ffc144208e66a98e9f405888.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 9]: /images/20211214/7de63681c74147e893b9dbeeb3a483cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 10]: /images/20211214/d6621ce1aa684a64883bc90658d80250.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 11]: /images/20211214/ef4f66b094344a8f891ceeacdaa119a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 12]: /images/20211214/a65923aae96744cc82db0fa7a665074e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 13]: /images/20211214/301973c304ac4c9791d59fca90f8e8b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 14]: /images/20211214/c478da4993714f0c9ce1e1a057666174.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 15]: /images/20211214/7245d64299034f96a0ad45d5af85f461.png