《恋上数据结构与算法》笔记（十六）：二叉堆

骑猪看日落 2022-12-31 01:13 58阅读 0赞

# 目录 #

*  一、二叉堆（Heap）
    
     *  1、问题
     *  2、二叉堆概念
     *  3、堆的接口设计
 *  二、二叉堆（Binary Heap）
 *  三、二叉堆（Binary Heap）接口实现
    
     *  1、构造方法
     *  2、添加
     *  3、删除
     *  4、replace操作
     *  5、批量建堆
     *  6、TopK问题
 *  四、leetcode算法题
 *  五、二叉堆代码(完整)

### 一、二叉堆（Heap） ###

#### 1、问题 ####

*  设计一种数据结构，用来存放整数，要求提`3`个接口。
    
     *  **`添加元素`**
     *  **`获取最大值`**
     *  **`删除最大值`**

![img][]

*  更优秀的数据结构：`堆`，获取最大值复杂度`O(1)`，删除最大值`O(logn)`，添加元素`O(logn)`
    
     *  删除最大值, 会造成`下滤`
     *  添加元素, 会造成`上滤`

#### 2、概念 ####

> 注意: 和我们平时提到的内存中的`堆`不是一回事 !

*  堆（Heap）在逻辑结构上是一种`树状(完全二叉树)`的数据结构, 物理结构上是`数组`结构。
 *  堆的一个重要性质：任意节点的值总是`大于等于`或`小于等于`子节点的值。
    
     *  如果任意节点的值总是大于等于子节点的值，称为`最大堆`，`大根堆`，`大顶堆`。
     *  反之称为`最小堆`，`小根堆`，`小顶堆`。

![img][img 1]

*  `最大堆`和`最小堆`的最大值/最小值都在`顶部`。且堆中的元素必须具备`可比较性`。

#### 3、堆的接口设计 ####

public interface Heap<E> { 
        int size();	// 元素的数量
        boolean isEmpty();	// 是否为空
        void clear();	// 清空
        void add(E element);	 // 添加元素
        E get();	// 获得堆顶元素
        E remove(); // 删除堆顶元素
        E replace(E element); // 删除堆顶元素的同时插入一个新元素
    }

### 二、二叉堆（Binary Heap） ###

*  `二叉堆`的逻辑结构就是一颗`完全二叉树`，所以也叫`完全二叉堆`。
 *  代码中, 需要用到很多`完全二叉树`的性质  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]

--------------------

*  二叉堆的物理结构使用`数组`来实现即可  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 5]
 *  鉴于`完全二叉树`的一些性质，**二叉堆的底层（物理结构）** 一般用`数组`实现即可。
 *  索引 `i` 的规律（n是元素数量）
    
     *  如果`i = 0`，它是`根`节点。
     *  如果`i > 0`，它的`父节点`的索引为`floor((i-1) / 2)`。
     *  如果`2i + 1 <= n - 1`，它的`左子节点`的索引为`2i + 1`。
     *  如果`2i + 1 > n - 1`，它`无`左子节点。
     *  如果`2i + 1 <= n - 1`，它的`右子节点`的索引为`2i + 2`。
     *  如果`2i + 1 > n - 1`，它`无`右子节点。

### 三、二叉堆（Binary Heap）接口实现 ###

##### 1、构造函数 #####

/* 批量建堆, 就是外界传过来一个无序的数组, 我们通过二叉堆的规则, 将该数组 变为一个二叉堆的结构 */
    public BinaryHeap(E[] elements, Comparator<E> comparator) { 
        super(comparator);
        // 外界传过来的数组为空,或者长度为0: 就无法批量建堆
        if (elements == null || elements.length == 0) { 
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else { 
            size = elements.length;
            // this.elements = elements; // 这样的话, 外面修改数组, 我们内部的数组也需要修改, 这样不好, 最好的方式就是深拷贝一份数据
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) { 
                this.elements[i] = elements[i];
            }
            // 批量建堆的方法
            heapify();
        }
    }
    
    public BinaryHeap(E[] elements) { 
        this(elements, null);
    }
    
    public BinaryHeap(Comparator<E> comparator) { 
        this(null, comparator);
    }
    
    public BinaryHeap() { 
        this(null, null);
    }

##### 2、添加 #####

![img][img 2]

*  **`添加操作`** 需要循环执行以下步骤：
    
     *  如果`node > 父节点`，则与父节点交换位置。
     *  如果`node <= 父节点`，或者`node没有父节点`，(符合二叉堆性质), 则退出循环。
 *  这个过程叫做`上滤（Sift Up）`，时间复杂度为`O(logn)`。

![img][img 3]

@Override
    public void add(E element) { 
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        // 上滤,当添加一个节点(数组的最后), 要恢复二叉堆的性质
        siftUp(size - 1);
    }
    
    private void elementNotNullCheck(E element) { 
        if (element == null)
            throw new IllegalArgumentException("Element must not be null");
    }
    
    private void ensureCapacity(int capacity) { 
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity)
            return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) { 
            newElements[i] = elements[i];
        }
        elements = newElements;
    }
    
    /** * 让index位置的元素上滤 * * @param index */
    private void siftUp(int index) { 
    // E e = elements[index];
    // // 必须要存在父节点, index > 0表示有父节点
    // while (index > 0) { 
    // // 获取父节点的索引. 根据公式, (index-1)/2
    // int pindex = (index - 1) >> 1;
    // E p = elements[pindex];
    // // 插入的节点 <= 父节点, 此时符合二叉堆性质,退出
    // if (compare(e, p) <= 0) return;
    // // 交换index, pindex位置的内容
    // E tmp = elements[index];
    // elements[index] = elements[pindex];
    // elements[pindex] = tmp;
    // // 重新赋值(继续上滤),循环判断
    // index = pindex;
    // }
    
        // 对比上面, 进行优化
        E element = elements[index];
        while (index > 0) { 
            int parentIndex = (index - 1) >> 1;
            E parent = elements[parentIndex];
            if (compare(element, parent) <= 0) break;
            // 将父元素存储在index位置
            elements[index] = parent;
            // 重新赋值index
            index = parentIndex;
        }
        elements[index] = element;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 7]

##### 3、删除 #####

> 删除的是堆顶元素, 也就是 最大/最小的节点

*  `首先用最后一个节点覆盖根节点`
 *  `然后删除最后一个节点`
 *  循环执行以下步骤（43简称为node）
    
     *  如果`node < 最大的子节点`，与最大的子节点交换位置。
     *  如果`node >= 最大的子节点`，或者`node`没有子节点，则退出循环。
 *  这个过程叫做`下滤（Sift Down）`，时间复杂度：`O(logn)`。

![img][img 4]

*  同样的，`交换位置`的操作可以像添加那样进行`优化`。

@Override
    public E remove() { 
        emptyCheck();
    
        E root = elements[0];
        // 将数组最后的节点,替代堆顶节点; 这样做的目的是为了减少移动,提高效率
        elements[0] = elements[size - 1];
        elements[size - 1] = null;	// 删除最后一个节点
        size--;
    
        // 最后一个元素放到数组索引0的位置后, 要进行下滤, 修复二叉堆性质
        siftDown(0);
        return root; // 返回的是删除的堆顶元素
    }
    
    private void emptyCheck() { 
        if (size == 0)
            throw new IndexOutOfBoundsException("Heap is empty");
    }
    
    /** * 让index位置的元素进行下滤操作, 最后一个元素放到数组索引0的位置后,可能不满足二叉堆的性质,要进行下滤, 修复二叉堆性质 * * @param index 需要进行下滤的节点, 肯定是非叶子节点,因为要和他的子节点比较, 得到堆顶元素 */
    private void siftDown(int index) { 
    	// 此时是上图2的 43
        E element = elements[index];
        // 非叶子节点的数量: 公式:floor (n / 2)
        int notLeafCount = size >> 1;
        /* 完全二叉树, 从上至下,从左向右,遇到的第一个叶子节点, 它后面的节点必然是叶子节点, 完全二叉树性质 也就是说, `当index小于第一个叶子节点的索引`, 那么index肯定不是叶子节点 第一个叶子节点的索引 = 非叶子节点的数量 = size / 2 */
    
        // 确保index位置的元素必须要有子节点, 然后和最大的子节点进行交换位置
        // 如果index位置的元素 大于 它的子节点, 则不需要交换, 符合二叉堆性质, 退出循环
        /* 第一个叶子节点的索引 = 非叶子节点的数量 index < 第一个非叶子节点的数量, 就表示它肯定是有子节点的 */
        while (index < notLeafCount) { 	// index的范围就是有子节点的节点
            // 表示index索引的节点肯定是非叶子节点
            // index节点有两种情况 (基于完全二叉树的性质)
            // 1. 只有左子节点
            // 2. 同时有左右子节点
            // 默认为 左子节点 跟 交换完的堆顶节点 比较 ;左子节点的索引:公式 2i+1,右子节点的索引: 2i+2 == 左子节点索引 + 1
            int childIndex = (index << 1) + 1;	// 左子节点的索引
            E child = elements[childIndex];
    
            // 右子节点
            int rightIndex = childIndex + 1;
            // 如果有左右节点, 选出最大的子节点
            // rightIndex < size表示算出来的右子节点的索引,是存在的
            // if的含义 : 右子节点存在 且 右子节点大于左子节点
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) { 
                childIndex = rightIndex;
                child = elements[rightIndex];
            }
    
            if (compare(element, child) >= 0) break; // 说明element交换过来的堆顶节点 大于它的子节点, 此时满足二叉堆性质,退出
    
            // 将子节点存放到index位置; `然后要将childIndex赋值给index`, 也就是说此时的堆顶节点跑到了childIndex的位置,
            // 所以要将更换堆顶节点index的值, 就需要使用 index = childIndex; 因为下一轮还是需要index的堆顶元素再和它的子节点比较, 以此类推
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 8]

##### 4、replace操作 #####

*  删除堆顶元素，并用新值替换。
 *  用新值替换堆顶，然后做`下滤`操作即可。

/** * 删除堆顶元素, 并添加一个元素 * * @param element * @return */
    @Override
    public E replace(E element) { 
        elementNotNullCheck(element);
        // 方式一: 两个O(logn)级别
    // E root = remove();
    // add(element);
    
        // 方式二: 可以将要添加的元素直接覆盖掉堆顶元素, 然后进行一次下滤操作即可; 这样的话就一次O(logn)
        E root = null;
        if (size == 0) {     // 表示数组中为空,堆中没有节点, 所以就不删除了, 但是可以添加
            elements[0] = element;
            size++;
        } else {  // 表示堆不为空, 将堆顶元素删除
            root = elements[0];
            elements[0] = element;
            siftDown(0); // 下滤
        }
        return root;
    }

##### 5、批量建堆 #####

*  批量建堆有两种做法
    
     *  自上而下的上滤
     *  **`自下而上的下滤`**
 *  自上而下的上滤：从上而下拿到每个元素，然后上滤。

![img][img 5]

*  自下而上的下滤：从下而上拿到每个元素，然后下滤。
    
     *  叶子节点无须下滤，所以从第一个非叶子节点开始操作。

![img][img 6]

*  效率比较：

![img][img 7]

*  **下滤执行最长操作的元素最少，而上滤需要执行最长操作的元素非常多。所以下滤效率更高。**

/** * 批量建堆 */
    private void heapify() { 
        // 自上而下的上滤 (效率不高,因为索引为0的位置就不需要上滤了,所以i从1开始)
        // for (int i = 1; i < size; i++) { 
        // siftUp(i);
        // }
    
        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) { 
            siftDown(i);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 9]

##### 5、TopK问题 #####

问题描述

*  从n个整数中, 找到最大的前k个数 (k远远小于n)

解决方法

*  使用排序算法, 进行全排序, 需要`O(nlogn)`的时间复杂度
 *  如果使用`二叉堆`来解决, 可以使用`O(nlogk)`的时间复杂度来解决

使用二叉堆解决的步骤

*  新建一个小顶堆
 *  扫n个整数
    
     *  先将遍历到的前k个数放入堆中
     *  从第`k+1`个数开始, 如果大于堆顶元素, 就使用`replace`操作 (删除对顶元素, 将第k+1个数添加到堆中)
 *  扫描完毕后, 堆中剩下的就是最大的`前k个数`

public static void main(String[] args) { 
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() { 
            @Override
            public int compare(Integer o1, Integer o2) { 
                return o2 - o1;
            }
        });
    
        // 找出最大的前k个数
        int k = 3;
        Integer[] data = { 51, 30, 39, 92, 74, 25, 16, 93,
                91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
                90, 6, 65, 49, 3, 26, 61, 21, 48};
        for (int i = 0; i < data.length; i++) { 
            if (heap.size() < k) {   // 将前k个数添加到小顶堆; 
                heap.add(data[i]);  // O(logk), 此时小顶堆有 51,30,39
            } else {     // 如果第k+1个数, 并且大于堆顶元素
                if (data[i] > heap.get()) { 
                    heap.replace(data[i]);  // O(logK)
                }
            }
        }
        BinaryTrees.println(heap);
    }

问题拓展

*  如果是找出最小的前k个数呢?
    
     *  用大顶堆
     *  如果小于堆顶元素, 就使用replace操作

### 四、leetcode算法题 ###

*  [最小K个数][K]

### 五、二叉堆代码(完整) ###

package com.guizy.heap;
    
    import com.guizy.printer.BinaryTreeInfo;
    
    import java.util.Comparator;
    
    /** * Description: 二叉堆(大顶堆) * * @author guizy1 * @date 2020/12/25 17:33 */
    @SuppressWarnings("unchecked")
    public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo { 
        private E[] elements;
        private static final int DEFAULT_CAPACITY = 10;
    
        /* 批量建堆, 就是外界传过来一个无序的数组, 我们通过二叉堆的规则, 将该数组 变为一个二叉堆的结构 */
        public BinaryHeap(E[] elements, Comparator<E> comparator) { 
            super(comparator);
            // 外界传过来的数组为空,或者长度为0: 就无法批量建堆
            if (elements == null || elements.length == 0) { 
                this.elements = (E[]) new Object[DEFAULT_CAPACITY];
            } else { 
                size = elements.length;
                // this.elements = elements; // 这样的话, 外面修改数组, 我们内部的数组也需要修改, 这样不好, 最好的方式就是深拷贝一份数据
                int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
                this.elements = (E[]) new Object[capacity];
                for (int i = 0; i < elements.length; i++) { 
                    this.elements[i] = elements[i];
                }
                // 批量建堆的方法
                heapify();
            }
        }
    
        public BinaryHeap(E[] elements) { 
            this(elements, null);
        }
    
        public BinaryHeap(Comparator<E> comparator) { 
            this(null, comparator);
        }
    
        public BinaryHeap() { 
            this(null, null);
        }
    
        @Override
        public void clear() { 
            for (int i = 0; i < size; i++) { 
                elements[i] = null;
            }
            size = 0;
        }
    
        @Override
        public void add(E element) { 
            elementNotNullCheck(element);
            ensureCapacity(size + 1);
            elements[size++] = element;
            // 上滤,当添加一个节点, 要恢复二叉堆的性质
            siftUp(size - 1);
        }
    
        @Override
        public E get() { 
            emptyCheck();
            return elements[0];
        }
    
        @Override
        public E remove() { 
            emptyCheck();
    
            E root = elements[0];
            // 将数组最后的节点,替代堆顶节点; 这样做的目的是为了减少移动,提高效率
            elements[0] = elements[size - 1];
            elements[size - 1] = null;
            size--;
    
            // 最后一个元素放到数组索引0的位置后, 要进行下滤, 修复二叉堆性质
            siftDown(0);
            return root;
        }
    
        /** * 删除堆顶元素, 并添加一个元素 * * @param element * @return */
        @Override
        public E replace(E element) { 
            elementNotNullCheck(element);
            // 方式一: 两个O(logn)级别
    // E root = remove();
    // add(element);
    
            // 方式二: 可以将要添加的元素直接覆盖掉堆顶元素, 然后进行一次下滤操作即可; 这样的话就一次O(logn)
            E root = null;
            if (size == 0) {     // 表示数组中为空,堆中没有节点, 所以就不删除了, 但是可以添加
                elements[0] = element;
                size++;
            } else {  // 表示堆不为空, 将堆顶元素删除
                root = elements[0];
                elements[0] = element;
                siftDown(0); // 下滤
            }
            return root;
        }
    
        /** * 批量建堆 */
        private void heapify() { 
            // 自上而下的上滤 (效率不高,因为索引为0的位置就不需要上滤了,所以i从1开始)
            // for (int i = 1; i < size; i++) { 
            // siftUp(i);
            // }
    
            // 自下而上的下滤
            for (int i = (size >> 1) - 1; i >= 0; i--) { 
                siftDown(i);
            }
        }
    
        /** * 让index位置的元素上滤 * * @param index */
        private void siftUp(int index) { 
    // E e = elements[index];
    // // 必须要存在父节点, index > 0表示有父节点
    // while (index > 0) { 
    // // 获取父节点的索引. 根据公式, (index-1)/2
    // int pindex = (index - 1) >> 1;
    // E p = elements[pindex];
    // // 插入的节点 <= 父节点, 此时符合二叉堆性质,退出
    // if (compare(e, p) <= 0) return;
    // // 交换index, pindex位置的内容
    // E tmp = elements[index];
    // elements[index] = elements[pindex];
    // elements[pindex] = tmp;
    // // 重新赋值(继续上滤),循环判断
    // index = pindex;
    // }
    
            // 对比上面, 进行优化
            E element = elements[index];
            while (index > 0) { 
                int parentIndex = (index - 1) >> 1;
                E parent = elements[parentIndex];
                if (compare(element, parent) <= 0) break;
                // 将父元素存储在index位置
                elements[index] = parent;
                // 重新赋值index
                index = parentIndex;
            }
            elements[index] = element;
        }
    
        /** * 让index位置的元素进行下滤操作, 最后一个元素放到数组索引0的位置后,可能不满足二叉堆的性质,要进行下滤, 修复二叉堆性质 * * @param index 需要进行下滤的节点, 肯定是非叶子节点,因为要和他的子节点比较, 得到堆顶元素 */
        private void siftDown(int index) { 
            E element = elements[index];
            // 非叶子节点的数量: 公式:floor (n / 2)
            int notLeafCount = size >> 1;
            /* 完全二叉树, 从上至下,从左向右,遇到的第一个叶子节点, 它后面的节点必然是叶子节点, 完全二叉树性质 也就是说, `当index小于第一个叶子节点的索引`, 那么index肯定不是叶子节点 第一个叶子节点的索引 = 非叶子节点的数量 = size / 2 */
    
            // 确保index位置的元素必须要有子节点, 然后和最大的子节点进行交换位置
            // 如果index位置的元素 大于 它的子节点, 则不需要交换, 符合二叉堆性质, 退出循环
            /* 第一个叶子节点的索引 = 非叶子节点的数量 index < 第一个非叶子节点的数量, 就表示它肯定是有子节点的 */
            while (index < notLeafCount) { 
                // 表示index索引的节点肯定是非叶子节点
                // index节点有两种情况 (基于完全二叉树的性质)
                // 1. 只有左子节点
                // 2. 同时有左右子节点
                // 默认为 左子节点 跟 交换完的堆顶节点 比较 ;左子节点的索引:公式 2i+1,右子节点的索引: 2i+2 == 左子节点索引 + 1
                int childIndex = (index << 1) + 1;
                E child = elements[childIndex];
    
                // 右子节点
                int rightIndex = childIndex + 1;
                // 如果有左右节点, 选出最大的子节点
                // // 表示算出来的右子节点的索引,是存在的, rightIndex < size 且 右子节点大于左子节点
                if (rightIndex < size && compare(elements[rightIndex], child) > 0) { 
                    childIndex = rightIndex;
                    child = elements[rightIndex];
                }
    
                if (compare(element, child) >= 0) break; // 说明element交换过来的堆顶节点 大于它的子节点, 此时满足二叉堆性质,退出
    
                // 将子节点存放到index位置; `然后要将childIndex赋值给index`, 也就是说此时的堆顶节点跑到了childIndex的位置,
                // 所以要将更换堆顶节点index的值, 就需要使用 index = childIndex; 因为下一轮还是需要index的堆顶元素再和它的子节点比较, 以此类推
                elements[index] = child;
                // 重新设置index
                index = childIndex;
            }
            elements[index] = element;
        }
    
        private void ensureCapacity(int capacity) { 
            int oldCapacity = elements.length;
            if (oldCapacity >= capacity)
                return;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) { 
                newElements[i] = elements[i];
            }
            elements = newElements;
        }
    
        private void emptyCheck() { 
            if (size == 0)
                throw new IndexOutOfBoundsException("Heap is empty");
        }
    
        private void elementNotNullCheck(E element) { 
            if (element == null)
                throw new IllegalArgumentException("Element must not be null");
        }
    
        @Override
        public Object root() { 
            // 返回的根节点, 就是数组0位置的元素
            return 0;
        }
    
        @Override
        public Object left(Object node) { 
            // 左索引 2 * index + 1
            int index = (int) node;
            index = (index << 1) + 1;
            // 因为index索引在数组中和size的关系, index从0开始, 所以肯定不能index>=size,越界
            return index >= size ? null : index;
        }
    
        @Override
        public Object right(Object node) { 
            int index = (int) node;
            index = (index << 1) + 2;
            return index >= size ? null : index;
        }
    
        @Override
        public Object string(Object node) { 
            return elements[(int) node];
        }
    }

[img]: /images/20221120/882d35f7c0384c96aaf7d43f63660cbf.png
[img 1]: /images/20221120/6304e976b96040c0a47ef5062b140579.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/db1715222cc64e8792c4a0c6007b501a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20221120/296770aac76a4397a552033165777b57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20221120/d54f9215539249848b0839a9e91aa487.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]: /images/20221120/a8d31aefc9c7447abdd07a31fd9335ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]: /images/20221120/622303b485644a968993db2e07aea259.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 5]: /images/20221120/725dd0801c9340149223ae64029e18ba.png
[img 2]: /images/20221120/36ef2d6447f7486390fec90dcd1fd5ad.png
[img 3]: /images/20221120/7fbd1c8b95b9488ea8d11297e96f9748.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 6]: /images/20221120/2005d4cf0c8848edad9d45b991641a67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 7]: /images/20221120/61b56618691e4c788e22d670381b619f.png
[img 4]: /images/20221120/2e2e8b57dc794b33918c93fc9ff4668b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 8]: /images/20221120/76de4b3299534d2184f604ba203d171d.png
[img 5]: /images/20221120/a2c5fadf743a4666a47cda4e921670c2.png
[img 6]: /images/20221120/bfbbc97a04304a3890f646e6e27c4367.png
[img 7]: /images/20221120/fcef6984fd624c0288c91510decfff2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 9]: /images/20221120/01d97e44d2fc4aa197b76a0457091f10.png
[K]: https://leetcode-cn.com/problems/smallest-k-lcci/