二十三、二叉堆

作者: 咸鱼Jay | 来源:发表于2022-02-09 14:51 被阅读0次

1、思考

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

有没有更优的数据结构？
堆：获取最大值：O(1)、删除最大值：O( $log{_n}$ )、添加元素：O( $log{_n}$ )

2、Top K问题

什么是 Top K 问题
- 从海量数据中找出前 K 个数据
比如
- 从 100 万个整数中找出最大的 100 个整数
Top K 问题的解法之一：可以用数据结构“堆”来解决

3、堆（Heap)

$\color{#00afef}{堆}$ （Heap）也是一种树状的数据结构（不要跟内存模型中的“堆空间”混淆），常见的堆实现有
$\color{#00afef}{二叉堆}$ （Binary Heap， $\color{#00afef}{完全二叉堆}$ ）
$\color{#00afef}{多叉堆}$ （D-heap、D-ary Heap）
$\color{#00afef}{索引堆}$ （Index Heap）
$\color{#00afef}{二项堆}$ （Binomial Heap）
$\color{#00afef}{斐波那契堆}$ （Fibonacci Heap）
$\color{#00afef}{左倾堆}$ （Leftist Heap， $\color{#00afef}{左式堆}$ ）
$\color{#00afef}{斜堆}$ （Skew Heap）
堆的一个重要性质：任意节点的值总是 $\color{red}{≥}$ （ $\color{red}{≤}$ ） $\color{#ed7d31}{子节点}$ 的值
- 如果任意节点的值总是 $\color{red}{≥}\color{#ed7d31}{子节点}$ 的值，称为： $\color{#00afef}{最大堆}$ 、 $\color{#00afef}{大根堆}$ 、 $\color{#00afef}{大顶堆}$
- 如果任意节点的值总是 $\color{red}{≤}\color{#ed7d31}{子节点}$ 的值，称为： $\color{#00afef}{最小堆}$ 、 $\color{#00afef}{小根堆}$ 、 $\color{#00afef}{小顶堆}$
由此可见，堆中的元素必须具备可比较性（跟二叉搜索树一样）

4、堆的基本接口设计

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

5、二叉堆（Binary Heap)

$\color{#00afef}{二叉堆}$ 的逻辑结构就是一棵完全二叉树，所以也叫 $\color{#00afef}{完全二叉堆}$
鉴于完全二叉树的一些特性， $\color{#00afef}{二叉堆}$ 的底层（物理结构）一般用数组实现即可
索引 i 的规律（ n 是元素数量）
- 如果 i = 0 ，它是 $\color{#ed7d31}{根}$ 节点
- 如果 i > 0 ，它的 $\color{#ed7d31}{父}$ 节点的索引为floor( $\color{red}{(i – 1) / 2}$ )
- 如果 2i + 1 ≤ n – 1，它的 $\color{#ed7d31}{左}$ 子节点的索引为 $\color{red}{2i + 1}$
- 如果 2i + 1 > n – 1 ，它 $\color{#ed7d31}{无左}$ 子节点
- 如果 2i + 2 ≤ n – 1 ，它的 $\color{#ed7d31}{右}$ 子节点的索引为 $\color{red}{2i + 2}$
- 如果 2i + 2 > n – 1 ，它 $\color{#ed7d31}{无右}$ 子节点

6、代码实现

6.1、二叉堆的构造函数及部分方法的实现

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;
    }
 
    ......  
    
    private void emptyCheck() {
        if(size == 0) {
            throw new IndexOutOfBoundsException("Heep is empty");
        }
    }
}

6.2、获取最大值

@Override
public E get() {
    emptyCheck();
    return elements[0];
}

private void emptyCheck() {
    if(size == 0) {
        throw new IndexOutOfBoundsException("Heep is empty");
    }
}

6.3、最大堆 - 添加

6.3.1、思路

循环执行以下操作（图中的简称为node）
- 如果node＞父节点,与父节点交换位置
- 如果node≤ 父节点，或者node没有父节点，退出循环
这个过程，叫做上滤（Sift Up）
- 时间复杂度：O( $log{_n}$ )

6.3.2、实现

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

private void ensureCapacity(int capacity) {
    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;
}

/**
 * 让index位置的元素上滤
 */
private void siftUp(int index) {
    E e = elements[index];
    while (index > 0) {
        int pindex = (index - 1) >> 1;// 性质：floor( (i - 1)/2 )
        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;
    }
}

6.3.3、打印调试

这里二叉堆的逻辑结构就是二叉树，所以这里是否可以使用之前的打印二叉树的方法来实现呢？
其实是可以的，虽然它的逻辑结构就是二叉树，而实际上是数据结构，但是可以将之前的打印方法进行特殊处理一下。

public class BinaryHeap<E> implements Heap<E> ,BinaryTreeInfo{
    ......

    @Override
    public Object root() {
        return 0;// 这里返回的是索引
    }

    @Override
    public Object left(Object node) {
        int index = ((int)node << 1) + 1;// 性质：左索引 2i + 1
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index = ((int)node << 1) + 2;// 性质：左索引 2i + 2
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        return elements[(int)node];
    }
}

6.3.4、最大堆 – 添加 – 交换位置的优化

上面的siftUp方法里进行交换时是需要三行代码，这个是可以进行优化的：先将新添加节点进行备份，在跟父节点进行比较时，父节点挪下来，但是新添加节点先不覆盖父节点，继续比较直到最后才把新添加节点覆盖父节点。

一般交换位置需要3行代码，可以进一步优化
- 将新添加节点备份，确定最终位置才摆放上去

仅从交换位置的代码角度看：
- 可以由大概的 $3 * O(log_n)$ 优化到 $1 * O(log_n) + 1$

private void siftUp(int index) {
    E e = elements[index];
    while (index > 0) {
        int pindex = (index - 1) >> 1;// 性质：floor( (i - 1)/2 )
        E p = elements[pindex];
        if(compare(e, p) <= 0) break;
        
        // 将父元素存储在index位置
        elements[index] = p;
        
        // 重新赋值index
        index = pindex;
    }
    elements[index] = e;
}

6.4、抽取堆父类

我们上面实现的是二叉堆，其实堆又很多种，二项堆、斐波那契堆、左倾堆等，但是不管你是什么堆都应该实现Heap接口，而且堆还分大根堆和小根堆，也就是说只要是堆它上面的元素都必须要具备可比较性的，那么现在完全可以将堆一些公共功能抽取出来。

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);
    }
}

6.5、最大堆 - 删除

6.5.1、思路

删除操作是删除堆顶元素，因为这里的二叉堆是用数组实现的，如果直接删除堆顶元素，则所有元素都需要向前挪动，性能太差。所以这里需要拿到数组的最后一个元素，先覆盖堆顶元素，然后在清空最后一个元素。覆盖后，肯定不具有最大堆了的性质了，堆顶元素肯定小于它的下面两个元素，所以现在还需要进行比较然后进行交换。

那么选择子节点的那个进行交换比较合适呢？当然是子节点的最大值。

6.5.2、下滤

用最后一个节点覆盖根节点
删除最后一个节点
循环执行以下操作（图中的 43 简称为node）

如果node< 最大的子节点，与最大的子节点交换位置
如果node≥ 最大的子节点，或者node没有子节点，退出循环
这个过程，叫做下滤（Sift Down），时间复杂度： $O(log_n)$
同样的，交换位置的操作可以像添加那样进行优化

public E remove() {
    emptyCheck();
    E root = elements[0];
    elements[0] = elements[size -1];
    elements[size -1] = null;
    size--;
    siftDown(0);// 下滤
    return root;
}

上面有两个地方都是用了size - 1，这里是可以进行优化的:

public E remove() {
    emptyCheck();
    E root = elements[0];
    int lastIndex = --size;
    elements[0] = elements[lastIndex];
    elements[lastIndex] = null;
    
    siftDown(0);// 下滤
    return root;
}

下面专心实现下滤siftDown的代码，实现下滤siftDown的代码是需要while循环，那么进入循环的条件就是下滤的节点必须要有子节点，也就是说必须是非叶子节点。我们通过之前讲的完全二叉树的性质可以知道：从上到下、从左到右排序，只要遇到第一个叶子节点，往后所有节点都是叶子节点。所以这里的下滤siftDown的参数index只有小于第一个叶子节点的索引，才能进入while循环

那么第一个叶子节点的索引怎么算呢？其实就是非叶子节点的数量( floor(n / 2) )。

private void siftDown(int index) {
    // 第一个叶子节点的索引 == 非叶子节点的数量
    while(index < 第一个叶子节点的索引) {// 必须保证index位置是非叶子节点
        
    }
}

根据之前《十、二叉树》中了解到计算非叶子节点个数的公式是：n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 ),因此可以实现下滤siftDown的具体代码

private void siftDown(int index) {
    E element = elements[index];
    int half = size >> 1; // floor(n / 2)
    // 第一个叶子节点的索引 == 非叶子节点的数量
    // index < 第一个叶子节点的索引
    while(index < half) {// 必须保证index位置是非叶子节点
        // index的节点有2种情况
        // 1.只有左子节点
        // 2.同时有左右子节点
        
        // 默认为左子节点跟它进行比较
        int childIndex = (index << 1) + 1;// 2i + 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;

        // 将子节点存放到index位置
        elements[index] = child;
        // 重新设置index
        index = childIndex;
    }
    elements[index] = element;
}

6.7、replace方法实现

6.7.1、思路

replace是删除堆顶元素的同时插入一个新元素
这里我们可以想到直接先删除，在添加操作就可以完成。

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

但是这样会有一点点的浪费，因为remove和add都是 $O(log_n)$ 级别的,所以这个replace也就是两个 $O(log_n)$ 级别。

6.7.2、实现

这里可以直接进行将要添加的元素直接替换堆顶元素，然后做下滤操作就可以了。

public E replace(E element) {
    elementNotNullCheck(element);
    
    E root = null;
    if (size == 0) {
        elements[0] = element;
        size++;
    }else {
        root = elements[0];
        elements[0] = element;
        siftDown(0);
    }
    return root;
}

7、最大堆 – 批量建堆（Heapify）

如果我有一批数据，如何批量插入到堆里呢？我们想到了可以直接利用for循环一个一个添加。

Integer[] 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]);
}
BinaryTrees.println(heap);

其实还有其它做法，而且有些做法可能效果更优。这里讲两种做法：

批量建堆，有 2 种做法
1. 自上而下的上滤
2. 自下而上的下滤

7.1、最大堆 – 批量建堆 – 自上而下的上滤

自上而下的上滤是从除了跟节点开始的(i = 1)
这个相当于添加操作，差不多等价于挨个添加

7.2、最大堆 – 批量建堆 – 自下而上的下滤

自下而上的下滤式从非叶子节点开始的((size >> 1) -1)，(size >> 1) -1就是上图的73的位置，它是最后一个非叶子节点，在完全二叉树中非叶子节点的数量是总节点数量的一半
这个相当于删除操作

7.3、最大堆 – 批量建堆 – 效率对比

所有节点的深度之和
- 仅仅是叶子节点，就有近 $\frac{n}{2}$ 个，而且每一个叶子节点的深度都是 $O(log_n)$ 级别的
- 因此，在叶子节点这一块，就达到了 $O(nlog_n)$ 级别
- $O(nlog_n)$ 的时间复杂度足以利用排序算法对所有节点进行全排序

所有节点的高度之和
- 假设是满树，节点总个数为 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 − log_2(n + 1) = O(n)$

公式推导

S(h) = $1 ∗ 2^1 + 2 ∗ 2^2 + 3 ∗ 2^3 + ⋯ + (h − 2) ∗ 2^{h−2} + (h − 1) ∗ 2^{h−1}$
2S(h) = $1 ∗ 2^2 + 2 ∗ 2^3 + 3 ∗ 2^4 + ⋯ + (h − 2) ∗ 2^{h−1} + h − 1 ∗ 2^h$
S(h) – 2S(h) = $[2^1 + 2^2 + 2^3 + ⋯ + 2^{h−1}] − (h − 1) ∗ 2^h = (2^h − 2) − h − 1 ∗ 2^h$
S(h) = $(h − 1) ∗ 2^h − (2^h − 2) = (h − 2) ∗ 2^h + 2$

疑惑

以下方法可以批量建堆么
- 自上而下的下滤
- 自下而上的上滤
述方法不可行，为什么？
- 认真思考【自上而下的上滤】、【自下而上的下滤】的本质
  - 自上而下的上滤本质其实就是等价于挨个添加
  - 自下而上滤的下本质其实就是先让其左右先变成一个堆，下滤后在变成堆

7.4、代码实现：

这里因为是直接将外面的数组赋值过来的(this.elements = elements;),所以外面一旦对数组进行了修改操作，那么就会导致有问题，因此这里需要对外面传过来的数据进行拷贝（深拷贝）

public BinaryHeap(E[] elements,Comparator<E> comparator) {
    super(comparator);
    if(elements == null || elements.length == 0) {
        this.elements = (E[]) new Object[DEFAULt_CAPACITY];
    }else {
        size = elements.length;
        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();
    }
}

8、最小堆

如何构建一个小顶堆呢？

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;// 最大堆
        return o2 - o1;// 最小堆
    }
});
BinaryTrees.println(heap);

9、Top K问题

从n个整数中，找出最大的前k个数（k远远小于n）
如果使用排序算法进行全排序，需要 $O(nlog_n)$ 的时间复杂度
如果使用二叉堆来解决，可以使用 $O(nlog_k)$ 的时间复杂度来解决
- 新建一个小顶堆
- 扫描n个整数
- 先将遍历到的前k个数放入堆中
- 从第k + 1个数开始，如果大于堆顶元素，就使用replace操作（删除堆顶元素，将第k + 1个数添加到堆中）
- 扫描完毕后，堆中剩下的就是最大的前k个数
如果是找出最小的前k个数呢？
- 用大顶堆
- 如果小于堆顶元素，就使用replace操作

// 新建一个小顶堆
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++) {
    int value = data[i];
    if(heap.size() < k) {// 前k个数添加到小顶堆
        heap.add(value);
    }else if(value > heap.get()){// 如果是第k + 1个数，并且大于堆顶元素
        heap.replace(value);
    }
}
BinaryTrees.println(heap);

这里先把前k个键入小顶堆里，以后的数据根堆顶的元素(小顶堆的堆顶元素是最小的)进行比较，如果大于堆顶元素，就会使用replace方法，先删除堆顶元素，最后在插入元素这样就达到了，找出最大的前k个数。

10、leetcode题：

215. 数组中的第K个最大元素

给定整数数组nums和整数k，请返回数组中第k个最大的元素。

请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

 class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();// 小顶端
        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];
            if(heap.size() < k) {// 前k个数添加到小顶堆
                heap.offer(value);
            }else if(value > heap.peek()){// 如果是第k + 1个数，并且大于堆顶元素
                heap.poll();
                heap.offer(value);
            }
        }
        return heap.peek();
    }
}

代码链接