小码哥《恋上数据结构与算法》笔记（十三）：二叉堆（Heap）

我的Github地址

小码哥《恋上数据结构与算法》笔记

极客时间《iOS开发高手课》笔记

iOS大厂面试高频算法题总结

iOS面试资料汇总

一、二叉堆（Heap）

1、思考

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

更优秀的数据结构：堆，获取最大值复杂度O(1)，删除最大值O(logn)，添加元素O(logn)

2、概念

堆（Heap）也是一种树状的数据结构
堆的一个重要性质：任意节点的值总是大于等于或小于等于子节点的值。
- 如果任意节点的值总是大于等于子节点的值，称为最大堆，大根堆，大顶堆。
- 反之称为最小堆，小根堆，小顶堆。
最大堆和最小堆的最大值/最小值都在顶部。且堆中的元素必须具备可比较性。

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）

二叉堆的逻辑结构就是一颗完全二叉树，所以也叫完全二叉堆。
鉴于完全二叉树的一些性质，二叉堆的底层（物理结构）一般用数组实现即可。
索引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);
		
    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();
    }	
}

2、添加

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

@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;
		
    // 新容量为旧容量的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位置的元素上滤
 * @param index
 */
private void siftUp(int index) {
    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; //当最终确认交换位置后，再将备份的值赋给新的位置。
}

3、删除

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

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

@Override
public E remove() {
    emptyCheck();
		
    int lastIndex = --size; //最后一个元素的索引
    E root = elements[0]; //拿出0位置的元素
    elements[0] = elements[lastIndex];
    elements[lastIndex] = null;
		
    siftDown(0); //下滤
    return root;
}

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

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

4、replace操作

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

@Override
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;
}

5、批量建堆

批量建堆有两种做法
- 自上而下的上滤
- 自下而上的下滤
自上而下的上滤：从上而下拿到每个元素，然后上滤。
自下而上的下滤：从下而上拿到每个元素，然后下滤。
- 叶子节点无须下滤，所以从第一个非叶子节点开始操作。
效率比较：
下滤执行最长操作的元素最少，而上滤需要执行最长操作的元素非常多。所以下滤效率更高。

四、leetcode算法题

最小K个数