Mofan
返回

数据结构之二叉堆

发表于 更新于
浏览量： --

文章目录

0%

封面画师：ツチヤ     封面ID：78809165

本文参考视频：小马哥教育(SEEMYGO) 2019 年 恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

0. 需求分析

现需要设计一种数据结构，用来存放整数，要求提供三个接口：

可以用很多方式来实现这个需求，比如动态数组、双向链表、BBST 等，它们的时间复杂度对比如下：

获取最大值删除最大值添加元素吐槽
动态数组 \ 双向链表O(n)O(n)O(1)
有序 动态数组 \ 双向链表O(1)O(1)O(n)全排序有点浪费
BBSTO(logn)O(logn)O(logn)杀鸡焉用牛刀？

通过上面的对比可知 BBST 的综合效率更高，难道就采用红黑树或 AVL 树来实现？

你是憨批

BBST 内部逻辑多复杂心里没点数？BBST 的功能也很强大，能做很多事，然后就拿来做这三个需求？那不是杀鸡用了牛刀？

那有没有更优的数据结构来实现呢？

那肯定是有的！ 可以使用 堆！😎

堆的时间复杂度如下：

获取最大值删除最大值添加元素
堆O(1)O(logn)O(logn)

至此还可以引入一个问题： Top K 问题。💃

Top K 问题

所谓 Top K 问题，就是从海量数据中找出前 K 个数据。

比如： 从 100 万个整数中找出最大的 100 个整数。

Top K 问题的解法之一： 可以用数据结构 「堆」 来解决。💪

1. 堆的含义

堆（Heap）也是一种树状的数据结构（不要跟内存模型中的「堆空间」混淆），常见的堆实现有：

本文主要介绍二叉堆！

堆的性质

堆有一个重要的性质：任意节点的值总是 大于等于 （或小于等于）其 子节点 的值。

如果任意节点的值总是 大于等于 其子节点的值，称为：最大堆、大根堆、大顶堆，但这并不是说上一层的节点值一定大于等于下一层的节点值。如：

最大堆_ 二叉堆

如果任意节点的值总是 小于等于 其子节点的值，称为：最小堆、小根堆、小顶堆，同样也不是说上一层的节点值就一定小于等于下一层的节点值。如：

最小堆_ 二叉堆

通过图示可以发现：对于最大堆，整个堆的最大值就是在最上面的根节点；对于最小堆，整个堆的最小值就是在最上面的根节点。

由此可见，堆中的元素必须具备可比较性（跟二叉搜索树一样）。

接口设计

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

2. 二叉堆

2.1 基本含义

二叉堆 的 逻辑结构 就是一棵完全二叉树，所以也叫 完全二叉堆。

二叉堆示意图：

二叉堆

鉴于完全二叉树的一些特性，二叉堆的底层（即物理结构）一般用数组实现即可。

那为什么不用二叉树或者链表作为物理结构呢？

针对上图给出的二叉堆示意图，其物理结构可以表示为：

二叉堆物理结构

索引 i 的规律（n 是元素数量）

如果 i = 0，它是 根 节点。

如果 i > 0，它的 父 节点索引为 floor((i - 1) / 2)。

如果 2i + 1 <= n - 1，它的 左 子节点索引为 2i + 1。

如果 2i + 1 > n - 1，它 无左 子节点。

如果 2i + 2 <= n - 1，它的 右 子节点索引为 2i + 2。

如果 2i + 2 > n - 1，它 无右 子节点。

2.2 基本接口实现

接下来基于二叉堆，编写一个最大堆。

创建实现 Heap 接口二叉堆 BinaryHeap 类。

由于二叉堆的底层是由数组实现的，因此需要成员变量 size 来表示二叉堆的长度，还需规定数组的默认容量，为编写扩容代码做准备。

二叉堆的逻辑结构是完全二叉搜索树，因此要求节点有可比较性。

针对以上说明，可以实现一些简单的方法：

/**
 * 二叉堆（最大堆）
 * @author 默烦
 * @date 2020/8/4
 */
public class BinaryHeap<E> implements Heap<E> {
    private E[] elements;
    private int size;
    private Comparator<E> comparator;
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(Comparator<E> comparator) {
        this.comparator = comparator;
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public BinaryHeap(){
        this(null);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) { }

    @Override
    public E get() { // 获取堆顶元素
        // 判断堆是否为空
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        return null;
    }

    @Override
    public E replace(E element) {
        return null;
    }

    private int compare(E e1, E e2){
        return comparator != null ? comparator.compare(e1, e2)
                : ((Comparable<E>) e1).compareTo(e2);
    }

    // 检查二叉堆 size 是否为 0
    private void emptyCheck(){
        if (size == 0){
            throw new IndexOutOfBoundsException("Heap is empty!");
        }
    }
}

2.3 添加元素

再次声明：具体实现是基于二叉堆的最大堆。

前文说到：二叉堆的物理结构是数组，那应该怎么添加元素呢？

直接这样？:raising_hand:

@Override
public void add(E element) {
    elements[size++] = element;
}

那肯定不是啊！咋可能这么简单。😏

添加思路

首先，要求添加的元素需要有可比较性，因此添加元素时必须判断是否为 null，对此可以写一个检测空值的方法然后在添加方法 add() 中调用：

private void elementNotNullCheck(E element){
    if (element == null){
        throw new IllegalArgumentException("element must not be null!");
    }
}

添加元素时还可能出现数组容量不够的情况，此时需要对数组进行扩容。这里可以使用在动态数组中编写的扩容方法 ensureCapacity()，这也要在 add() 方法中调用：

// 保证要有capacity的容量(不考虑线程安全)
private void ensureCapacity(int capacity){
    // 当前 elements.length 为 10，因为默认容量为 10
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    // 新容量为新容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

还有最最重要的一点： 如果直接在数组末尾添加元素，可能会破坏二叉堆的结构，因此添加元素后需要对二叉堆的结构进行修复。

假设在一个二叉堆中添加元素 80，那么修复步骤如下：

二叉堆添加示意图

对上图的修复步骤进行总结（图中的 80 简称为 node）：

循环执行以下操作：

这个过程被称为上滤（Sift Up）。添加元素的时间复杂度为 O(logn)。

添加元素的实现

编写一个方法，这个方法可以让索引 index 位置的元素进行上滤：

/**
 * 让索引为 index 的元素进行上滤
 *
 * @param index 数组索引
 */
private void siftUp(int index) {
    E e = elements[index];
    while (index > 0) { // 索引位置节点有父节点时
        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
        index = pIndex;
    }
}

最后，在添加方法 add() 中对三个私有方法进行汇总：

@Override
public void add(E element) {
    elementNotNullCheck(element);
    ensureCapacity(size + 1);
    elements[size++] = element;
    siftUp(size - 1);
}

2.4 代码优化

上滤优化

上滤 siftUp() 的具体实现中进行了位置交换，而位置交换的代码需要三行，这里还可以进行优化：将新添加节点备份，确定最终位置后才摆放上去。

好像有点抽象？💫具体而言：

具体流程图如下：

二叉堆上滤优化流程

代码修改如下：

/**
* 让索引为 index 的元素进行上滤
*
* @param index 数组索引
*/
private void siftUp(int index) {
    E e = elements[index];
    while (index > 0) { // 索引位置节点有父节点时
        int pIndex = (index - 1) >> 1; // 获取父节点索引
        E p = elements[pIndex];
        if (compare(e, p) <= 0) break;

        // 将父元素存储在 index 位置
        elements[index] = elements[pIndex];
        // 重新赋值 index
        index = pIndex;
    }
    elements[index] = e;
}

对比未优化的代码可以发现，在 while 循环中减少了三条语句。

仅从交换位置的代码角度看：大概由 3 * O(logn) 优化到 1 * O(logn) + 1。

代码抽取

介绍堆的时候列举过很多的堆实现，比如：多叉堆、索引堆、斐波那契堆等等。有这么多的堆实现，它们中肯定有些代码是可以复用的，因此可以将这些公共代码抽取出来。

创建一个抽象类 AbstractHeap，实现 Heap 接口，用于抽取堆中的公共代码。

堆中的元素肯定是有可比较性的，同时成员变量 size 也肯定是每个堆都有的。基于 size 成员变量，size() 方法和 isEmpty() 方法也应该都是可以共用的，比较方法 compare() 也不例外。

PS： 注意抽象类中方法、成员变量的访问修饰符！

/**
 * @author 默烦
 * @date 2020/8/4
 */
public abstract class AbstractHeap<E> implements Heap<E> {
    protected int size;
    protected Comparator<E> comparator;

    public AbstractHeap(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public AbstractHeap() {
        this(null);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    protected int compare(E e1, E e2) {
        return comparator != null ? comparator.compare(e1, e2)
                : ((Comparable<E>) e1).compareTo(e2);
    }
}

然后可以用 BinaryHeap 继承抽象类 AbstractHeap，取消实现 Heap，并将 BinaryHeap 类中的公共方法、公共成员变量删除：

public class BinaryHeap<E> extends AbstractHeap<E> {
    // 删除了两个存在于父类的成员变量
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    // 这个构造方法也要修改
    public BinaryHeap(Comparator<E> comparator) {
        super(comparator);
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    // 删除方法 size()、isEmpty() 和 compare()
    
    // 省略其他代码
    ...
}

2.5 删除元素

删除元素的抽象方法是： E remove();，方法并没有接收任何参数，这意味着不能在这里的堆中删除指定的元素，其含义指的是 删除堆顶的元素 。

那应该怎么删除？ :raising_hand:

直接删除物理结构中数组中的元素，然后让后面的元素向前移，就和动态数组一样？

那肯定不是，如果这样的话，删除元素的时间复杂度就高达 O(n) 了。😥

删除思路

假设现有一个二叉堆如下图所示，需要删除其堆顶元素 80，具体删除步骤如下：

二叉堆删除示意图

对上述删除步骤进行总结：

在添加元素中存在上滤，既然有上滤，那么就有下滤，这里的过程就叫做下滤（Sift Down），时间复杂度为：O(logn)，同样在下滤中交换位置的操作也可以像上滤那样进行优化。

删除实现

首先得搞清楚循环的条件，其实很简单：循环到第一个叶子节点就停止循环。

因此得找到第一个叶子节点的索引，二叉堆的逻辑结构是一棵完全二叉树，根据完全二叉树的规律可知： 第一个叶子节点的索引等于非叶子节点的数量。

在完全二叉树中，非叶子节点的数量为 floor(n / 2)，其中 n 为节点的总数量。这样，循环条件就确定了！👏

然后就是找到节点的左右节点，并与其中最大的节点进行比较替换。这里有一点可以注意一下，在完全二叉树中，一个节点要么只有左子节点，要么左右子节点都有，不可能出现只有右子节点的情况，因此可以设置默认的比较节点为左子节点。

编写一个方法，这个方法可以让索引 index 位置的元素进行下滤：

/**
* 让索引为 index 的元素进行下滤
*
* @param index
*/
private void siftDown(int index) {
    E element = elements[index];
    int half = size >> 1;
    // 第一个叶子节点的索引 = 非叶子节点的数量
    while (index < half){ // 必须保证index位置是非叶子节点
        /*
         * index 位置的节点的子节点有两种情况
         * 1. 只有左子节点
         * 2. 同时有左子节点、右子节点
         */
        // 默认为左子节点的索引
        int childIndex = (index << 1) + 1;
        E child = elements[childIndex];

        // 右子节点索引
        int rightIndex = childIndex + 1;
        // 选出最大的子节点
        if (rightIndex < size 
            && compare(elements[rightIndex],child) > 0){
            //                childIndex = rightIndex;
            child = elements[childIndex = rightIndex];
        }

        if (compare(element,child) >= 0) break;
        // 将子节点存放到index位置
        elements[index] = child;
        // 重新设置index
        index = childIndex;
    }
    elements[index] = element;
}

最后，完善一下删除堆顶方法 remove()：

@Override
public E remove() { // 删除堆顶元素
    emptyCheck();

    int lastIndex = --size;
    E root = elements[0];
    elements[0] = elements[lastIndex];
    elements[lastIndex] = null;

    siftDown(0);
    return root;
}

2.6 replace 方法

replace 方法的完整签名是 E replace(E element);，表示删除堆顶元素的同时插入一个新元素。

既然如此，不难想到这么实现 replace() 方法：

@Override
public E replace(E element) {
    E root = remove();
    add(element);
    return root;
}

这么做…

确实可以。😂

但有点欠妥，因为删除、添加都是 O(logn) 级别的，俩加在一起就是 2 倍了，这样就有点 「浪费」。

因此，Duck 不必！

duck不必

那咋做呢？😳

删除栈顶元素的做法是：使用堆底元素覆盖堆顶元素，然后对堆进行修复，使用下滤操作。

根据这个启发，在实现 replace 时可以 使用替换元素覆盖堆顶元素，然后进行下滤操作。

replace() 方法的完整实现如下（注意部分特殊情况）：

@Override
public E replace(E element) {
    elementNotNullCheck(element);

    E root = null;
    if (size == 0) {
        elements[0] = element;
        size = 1;
    } else {
        root = elements[0];
        elements[0] = element;
        siftDown(0);
    }

    return root;
}

3. 批量建堆

3.1 基本含义

批量建堆（Heapify），就是将一组不满足堆要求的数据形成一个堆。（我自己的理解，可能不大准确 😜）

假设现有一组数据，它们是乱的、无规则的，想要把它们构造成一个堆，这就是 批量建堆。

那这好做！:raising_hand:

public static void main(String[] args) {
    int[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    BinaryHeap<Integer> heap = new BinaryHeap<>();
    for (int i = 0; i < data.length; i++) {
        heap.add(data[i]);
    }
}

这样不就完事了？

这么做也确实可以，但是没有必要！

可以但没必要

还有更好的做法：

3.2 自上而下的上滤

现有如下图所示的一组数据，它不满足：任意节点的值总是 大于等于 （或小于等于）其 子节点 的值。因此，它不是一个堆，但可以看成一棵二叉树。

接下来对这组数据进行改造，将其变为一个堆。

批量建堆的数据

首先采用的做法是： 自上而下的上滤。

这啥意思呢？就是按照从上到下，从左到右的顺序，对这些数据进行上滤操作。

即：按照 { 30, 34, 73, 60, 68, 43 } 的顺序进行上滤。

进行上滤时第一个元素可以不用进行上滤，因为它已经是第一个元素了，上滤个 🔨。

使用上述的数据，自上而下的上滤示意图为：

自上而下的上滤示意图

通过示意图可以发现，每进行一次上滤，观察局部都是一个最大堆，比如在第三步中，{73, 30, 34} 就是一个堆。持续进行上滤，直到整个结构都变成堆。

自上而下的上滤的本质是： 每进行一次上滤，就向堆中添加一个元素，堆慢慢长大，最终成为一个「大堆」，与添加 add() 类似。

上述过程可以像这样实现：

for(int i = 1; i < size; i++){
    siftUp(i);
}

3.2 自下而上的下滤

自上而下的上滤已经介绍完了，那么自下而上的下滤也就很好理解了。

自下而上的下滤：就是按照从下到上，从右到左的顺序，对这些数据进行下滤操作。

还是使用这样的一组数据：

批量建堆的数据

自下而上的下滤顺序为： {43, 68, 60, 73, 34, 30}

和上滤一样，下滤时也要注意一点： 叶子节点不用进行下滤，因为下滤是使用当前节点和其最大子节点进行交换，叶子节点都没子节点，交换个 🔨。

使用上述的数据，自下而上的下滤示意图如下：

自下而上的下滤示意图

通过示意图，我们可以发现，每进行一次下滤，观察局部都是一个最大堆。

比如在第二步中，{73, 43} 就是一个堆。

在第三步中，{68, 60, 34} 也是一个堆，这时就差 30 进行下滤了。

最后就和 replace() 的情况一样了，其他部分都是满足堆的结构，只要将首元素下滤后，整个结构就满足堆的结构了。

自下而上的下滤的本质是： 先形成多个较小的堆，然后把这些堆聚在一起，直接形成一个「大堆」。与 remove() 的后半部分类似。

上述过程可以像这样实现：

for(int i = (size >> 1) - 1; i >= 0; i--){
    siftDown(i);
}

3.3 效率对比

前文说了，自上而下的上滤相当于添加操作，而自下而上的下滤相当于删除的后半部分。

从对节点的操作数量来看，上滤仅有首节点没进行上滤，下滤则是叶子结点都不进行下滤。

这样一对比，似乎 自下而上的下滤 的效率更高。😕

实际结果也确实如此。😏

通过下图进行对比：

图中的三角形表示一个完全二叉树，将其分成四层，每一层所占的阴影部分面积不一样，面积越大，表示那一层的节点越多。

对于自上而下的上滤：第一层进行上滤的高度为 4 层，第二层进行上滤的高度为 3 层 ······

对于自下而上的下滤：第一层进行上滤的高度为 1 层，第二层进行上滤的高度为 2 层 ······

很显然，对于自上而下的上滤来说，有大量的节点进行上滤的高度为 4 层，而对于自下而上的下滤来说，只有第四层节点进行上滤的高度为 4 层。

批量建堆效率对比

因此不难得出：自下而上的下滤的效率更高。

3.4 复杂度

先直接上结论：

堆中的数据不是全排序的，是偏序的，就是说数据是稍微有序的，只能保证「任意节点的值总是大于等于 （或小于等于）其 子节点 的值」，但对于节点的「孙子节点」就不好说了。

而自上而下的上滤的复杂度高达 O(ologn)，这足以进行全排序了，但得到的结构却是偏序的，那岂不是很浪费？

对这两种复杂度：

所有节点的深度之和

仅仅是叶子节点，就有将近 n / 2 个，而且每一个叶子节点的深度都是 O(logn) 级别的。

因此，在叶子节点这一块，就达到了 O(nlogn) 级别。

O(nlogn) 的时间复杂度也足以利用排序算法对所有节点进行全排序了。

所有节点的高度之和

假设是满树，节点的总个数为 n，树高为 h，那么 n = 2^h^ - 1

所有节点的树高之和 H(n) = 2^0^ * (h - 0) + 2^1^ * (h - 1) + 2^2^ * (h - 2) + ··· + 2^h-1^ * [h - (h - 1)]

H(n) = h * (2^0^ + 2^1^ + 2^2^ + … + 2^h-1^) - [1 * 2^1^ + 2 * 2^2^ + 3 * 2^3^ + … + (h - 1) * 2^h-1^]

H(n) = h * (2^h^ - 1) - [(h - 2) * 2^h^ + 2]

H(n) = h * 2^h^ - h - h * 2^h^ + 2^h+1^ - 2

H(n) = 2^h+1^ - h - 2 = 2 * (2^h^ - 1) - h = 2n - h = 2n - log2(n + 1) = O(n)

上述公式推导涉及到一个错位相减，来复习一下高中数学 😂

节点高度和公式推导

3.5 拓展思考

前文提到：自上而下的上滤 和 自下而上的下滤 可以进行批量建堆。

那么，以下方法可以进行批量建堆吗？

答案是不行。😝

通过思考【自上而下的上滤】和【自下而上的下滤】的本质就可以得出答案，前者是添加，后者是删除。

而上面提到的两种方式毫无意义而言，因此是不行。

为了便于阅读，给一组数据方便测试：

Heapify拓展思考测试数据

3.6 代码实现

在 BinaryHeap 类中编写一个构造方法，此构造方法接收一个数组，并利用数组中的数据构建出包含数组数据的堆：

public BinaryHeap(E[] elements, Comparator<E> comparator){
        super(comparator);
        if (elements == null || elements.length == 0){
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            // 记得将size复制，不然只会存储第一个元素
            size = elements.length;
            // 保证容量至少为 10
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
//            this.elements = elements;
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }

在上述代码中，可以发现有一条语句被注释了：this.elements = elements;

使用这条语句的意思是用堆中的数组指向外部的数组，这么做有一个大问题：如果外部数组的数据发生改变，堆内的数据也会发生改变，这显然是不对的。因此只能将外部数据拷贝一份，再进行批量建堆。

由于添加了一个构造方法，需要对其他构造方法进行修改：

public BinaryHeap(E[] elements){
    this(elements, null);
}

public BinaryHeap(Comparator<E> comparator) {
    this(null, comparator);
}

public BinaryHeap() {
    this(null, null);
}

最后就是 heapify() 方法的代码了，其实也很简单，在前文已经分析过了：

/**
* 批量建堆 堆化
*/
private void heapify(){
    // 自上而下的上滤
    //        for (int i = 0; i < size; i++) {
    //            siftUp(i);
    //        }
    // 自下而上的下滤
    for (int i = (size >> 1) - 1; i >= 0; i--) {
        siftDown(i);
    }
}

3.7 二叉堆完整代码

/**
 * 二叉堆（最大堆）
 *
 * @author 默烦
 * @date 2020/8/4
 */
public class BinaryHeap<E> extends AbstractHeap<E>{
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(E[] elements, Comparator<E> comparator){
        super(comparator);
        if (elements == null || elements.length == 0){
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            // 记得将size复制，不然只会存储第一个元素
            size = elements.length;
            // 保证容量至少为 10
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
//            this.elements = elements;
            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();

        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;

        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);

        E root = null;
        if (size == 0) {
            elements[0] = element;
            size = 1;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }

        return root;
    }

    /**
     * 批量建堆 堆化
     */
    private void heapify(){
        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 让索引为 index 的元素进行下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子节点的索引 = 非叶子节点的数量
        while (index < half) { // 必须保证index位置是非叶子节点
            /**
             * index 位置的节点的子节点有两种情况
             * 1. 只有左子节点
             * 2. 同时有左子节点、右子节点
             */
            // 默认为左子节点的索引
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            // 右子节点索引
            int rightIndex = childIndex + 1;
            // 选出最大的子节点
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
//                childIndex = rightIndex;
                child = elements[childIndex = rightIndex];
            }

            if (compare(element, child) >= 0) break;
            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

    /**
     * 让索引为 index 的元素进行上滤
     *
     * @param index 数组索引
     */
    private void siftUp(int index) {
        E e = elements[index];
        while (index > 0) { // 索引位置节点有父节点时
            int pIndex = (index - 1) >> 1; // 获取父节点索引
            E p = elements[pIndex];
            if (compare(e, p) <= 0) break;

            // 将父元素存储在 index 位置
            elements[index] = elements[pIndex];
            // 重新赋值 index
            index = pIndex;
        }
        elements[index] = e;
    }

    // 保证要有capacity的容量(不考虑线程安全)
    private void ensureCapacity(int capacity) {
        // 当前elements.length 为 10，因为默认容量为10
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        // 新容量为新容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    // 检查二叉堆 size 是否为 0
    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!");
        }
    }
}

4. 举一反三

4.1 构建最小堆

前文实现了一个二叉堆中的最大堆，所谓最大堆，就是指任意节点一定不小于它的子节点。

那么怎么构建一个最小堆呢？:raising_hand:

这简单，把最大堆的代码复制一份，然后把里面的比较逻辑改一改，比如在下滤方法 siftDown() 方法中，将大于改成小于，小于改成大于，如：

private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        while (index < half) { // 必须保证index位置是非叶子节点
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            int rightIndex = childIndex + 1;
            // 最小堆构建，修改比较逻辑
            if (rightIndex < size && compare(elements[rightIndex], child) < 0) {
                child = elements[childIndex = rightIndex];
            }
            // 最小堆构建，修改比较逻辑
            if (compare(element, child) <= 0) break;
            elements[index] = child;
            index = childIndex;
        }
        elements[index] = element;
    }

同理，上滤方法 siftUp() 也是同样的修改方式。

这…可以是可以，但是不够优雅。😰

其实还有更简单的方法，堆中的数据都有可比较性，这些数据要么实现 Comparable 接口，要么在构建堆时使用自定义的比较器。堆中对元素进行比较的实现如下：

protected int compare(E e1, E e2) {
    return comparator != null ? comparator.compare(e1, e2)
            : ((Comparable<E>) e1).compareTo(e2);
}

当 compare() 方法的返回值大于 0 时，表示 e1 比较大；当返回值小于 0 时，表示 e2 比较大；当返回值等于 0 时，表示 e1 和 e2 相等。

对，就是比较器！可以使用比较器：

static void test(){
    Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
}

像上述这样使用比较器并重写 compare() 方法后，就相当于为数据指定了一套比较规则。

比较器中 compare() 方法中的 返回值如果大于 0 时，表示 o1 比较大 ；当返回值小于 0 时，表示 o2 比较大；当返回值等于 0 时，表示 o1 和 o2 相等。

假设 o1 为 20，o2 为 10，这个时候 o1 - o2 是大于 0，就表示 o1 相对于 o2 是较大的，而 o1 的数值也是大于 o2 的数值的。又假设 o1 为 10，o2 为 20，这个时候 o1 - o2 是小于 0，就表示 o1 相对于 o2 是较小的，而 o2 的数值也是大于 o1 的数值的。简单来说，在这种情况下，数值大的数据就比较大。

使用这种方式得到的二叉堆如下图：

数值大较大的二叉堆

那么如果换种方式，使用 o2 - o1 呢？即：

static void test(){
    Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    BinaryTrees.println(heap);
}

假设 o1 为 20，o2 为 10，这个时候 o2 - o1 是小于 0，就表示 o1 相对于 o2 是较小的，而 o1 的数值却小于 o2 的数值的。又假设 o1 为 10，o2 为 20，这个时候 o2 - o1 是大于 0，就表示 o1 相对于 o2 是较大的，而 o2 的数值却大于 o1 的数值的。简单来说，在这种情况下，数值小的数据就比较大。

在以前实现的二叉堆中，默认是最大堆，就是任意节点不小于其子节点，也就是说，任意节点相对于其子节点是较大的。

正因如此，如果使用 o1 - o2 表示数值较大的数据比较大，那么构建出来的最大堆中任意节点的数值是不小于其子节点的，这是个真正意义的最大堆。如果使用 o2 - o1 表示数值较小的数据比较大，那么构建出来的最大堆中任意节点的数值是不大于其子节点，这个时候，与其说是最大堆，不如说是最小堆。

使用 o2 - o1 后得到的二叉堆如下图：

数值小较大的二叉堆

总结

说了那么多，总结一下：

默认实现的是最大堆，但可以修改比较方式，让这个堆看起来是一个最大堆或最小堆。

注意： 理解 「数值较大」 和 「节点较大」 的区别，理解 「实现的是最大堆」 和 「看起来是最大堆或最小堆」 的区别。

4.2 Top K 问题

Top K 问题：从 n 个整数中，找出最大的前 k 个数。（k 远远小于 n）

有两种解决方式：

由于 k 远远小于 n，因此第二种方式是更好的，选择使用二叉堆来解决。

具体思路

1、新建一个小顶堆（不是找最大吗？为啥用小顶堆？😕别急，待会解释 😎）

2、扫描 n 个整数

3、扫描完毕后，堆中剩下的就是最大的前 k 个数

代码实现

假设现有 30 个数，找出其中最大的前 5 个数：

static void topK() {
    // 新建一个小顶堆
    BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    // 找出最大的前k个数
    int k = 5;
    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]); // logk
        } else if (data[i] > heap.get()) { // 如果是第 k+1个数，并大于堆顶元素
            heap.replace(data[i]); // // logk
        }
    }
    // O(nlogk)
}

最终得到的前 5 个数是：76、90、93、92、91

为什么要用小顶堆？

假定小顶堆中的元素是目标数组中最大的几个数。小顶堆的堆顶元素是整个堆中最小的，如果第 k + 1 个数大于堆顶元素，那么它一定该在这个小顶堆中。这个时候删除堆顶元素，将第 k + 1 个数添加到堆中，使得原本这个堆中的最小元素变大了，也保持小顶堆中的元素是目标数组中最大的几个数。一直循环扫描，堆中最小的元素不断变大，最后堆中的元素一定真正是那 n 个数中最大的前 k 个数。

使用堆解决 Top K 问题的时间复杂度为 O(nlogk) 是怎么计算的？

二叉堆添加元素的时间复杂度为 O(logn)，其中的 n 表示堆中的元素。在这个问题中，堆中元素是 k 个，因此 add() 方法的时间复杂度为 O(logk)。对于 replace() 方法也是如此，时间复杂度为 O(logk)。在上述代码中涉及两个判断，这两个判断中一个判断成功后调用 add() 方法，另一个判断成功后调用 replace() 方法，假设在最坏情况下，不是调用 add() 就是调用 replace()，那么这样的时间复杂度为 O(nlogk)，n 为数据总数。最终，使用堆解决 Top K 问题的时间复杂度就为 O(nlogk)。

如果是找出最小的前 k 个数应该怎么办？

使用大顶堆，其他操作一样，只不过第 k + 1 个元素小于堆顶元素时，使用 replace 操作。

如果这篇文章对你有帮助，可以通过
支付宝
支付宝
微信
微信
请我喝杯 Coffee ☕
上一篇
数据结构之优先级队列
下一篇
数据结构之哈希表