二十三、二叉堆

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

二十三、二叉堆
用go实现二叉堆插入删除构建
[数据结构与算法-iOS 实现]二叉堆原理实现及top k 问题
二叉堆
二叉堆(Binary Heap)
堆排序(下)：最大堆
二叉堆的Python实现
Sort.堆排序（heapsort） & 优先队列
二叉树（二）-二叉堆
PriorityQueue源码解析

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

代码链接

二十三、二叉堆
1、思考设计一种数据结构，用来存放整数，要求提供 3 个接口1. 添加元素2. 获取最大值3. 删除最大值有没...
用go实现二叉堆插入删除构建
二叉堆的插入：二叉堆的删除：二叉堆的构建：
[数据结构与算法-iOS 实现]二叉堆原理实现及top k 问题
二叉堆 demo 二叉堆其实就是一颗完全二叉树，所以又可以叫做完全二叉堆二叉堆的底层可以用数组来实现对于二叉堆...
二叉堆
二叉堆定义二叉堆是一种特殊的堆, 二叉堆是完全二叉树或者近似完全二叉树. 二叉堆满足堆特性: 父节点的键值总是保...
二叉堆(Binary Heap)
二叉堆这个数据结构有点意思，自己做了个总结，内容结构如下：二叉堆性质二叉堆操作应用二叉堆性质：堆（Hea...
堆排序(下)：最大堆
二叉堆，简称堆 Heap 尖的完全二叉树。也有三叉堆以及普通堆，但大部分时候堆就是指二叉堆二叉堆的定义一棵完全...
二叉堆的Python实现
二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的...
Sort.堆排序（heapsort） & 优先队列
二叉堆这个二叉堆和先进后出的那个堆不是一个。而且这个二叉堆从下标1开始存储元素。这里的二叉堆是个数组，也可以看...
二叉树（二）-二叉堆
1.什么是二叉堆二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：...
PriorityQueue源码解析
PriorityQueue 一个基于优先级堆的无界优先级队列。二叉堆可视化操作：二叉堆二叉堆(The bin...