二叉堆 - Java 实现

二叉堆定义

二叉堆是一棵完全二叉树，除最后一层外，每一层都是满的，且最后一层的节点从左到右依次生长。

此处实现的是最小二叉堆。

任何一个父节点的关键码总是小于、等于其子节点的关键码。

对于节点 $i$i，其左孩子为 $2 i$2i，右孩子为 $2i+1$2i+1，父节点为 $\lfloor i/2 \rfloor$⌊i/2⌋ 。

import java.util.ArrayList;
import java.util.List;

public class BinaryHeap<T extends Comparable<? super T>> {
    private List<T> list;

    public BinaryHeap() {
        list = new ArrayList<>();
        list.add(null);			// 索引为 0 的节点为哨兵，真正的节点数据从索引 1 处开始
    }

	// 节点数
    public int size() {
        return list.size() - 1;
    }
    ...
}

插入元素

设待插入元素为 e。

首先在最后一个位置创建一个空穴，并暂时用 e 填充它，然后执行上滤操作。

上滤

设空穴节点之父为 p 。若 e 小于 p 的关键码，则将 p 下沉至空穴处，空穴上升至 p 处。继续此过程，直至 e 能够放入空穴中。

注意：在执行上滤操作之前，首先将索引为 0 的哨兵节点的关键码设为 e 。该哨兵节点可看成是二叉堆的根节点之父。这样可使空穴最多上升至根节点（因为根节点之父的关键码为 e ，不小于 e）。

// 插入元素
public void insert(T e) {
    list.add(e);            // 在末尾添加一个空洞，暂时用 e 填充它
    int hole = size();

    percolateUp(hole);
}

// 上滤
private void percolateUp(int hole) {
    T e = list.get(hole);
    list.set(0, e);         // 哨兵

    // 只要 e 比空洞的父节点小，便将父节点往下拉，然后空洞上升
    while (e.compareTo(list.get(hole >> 1)) < 0) {
        list.set(hole, list.get(hole >> 1));
        hole >>= 1;
    }

    list.set(hole, e);
}

删除最小元素

最小元素在二叉堆的根节点处。

删除根节点后，将在根节点处产生一个空穴，且堆的大小将减少一。

可以首先删除最后一个节点，并暂时用它填充空穴，然后执行下滤操作。

下滤

设最后一个节点（删除操作之前）的关键码为 e 。

设空穴所在节点的最小孩子为 c，若 c 的关键码小于 e，则 c 上升至空穴处，空穴下沉至 c 处。重复此过程，直至 e 可放入空穴。

// 删除最小元素
public T removeMinimum() {
	// 堆为空
    if (size() < 1) {
        return null;
    }

    T minimum = list.get(1);		// 最小元素
    T last = list.remove(size());

	// 删除之后，堆不为空：原先堆至少有两个节点
    if (size() > 0) {
        list.set(1, last);
        percolateDown(1);
    }

    return minimum;
}

// 下滤
private void percolateDown(int hole) {
    T e = list.get(hole);
    int n = size();

    while ((hole << 1) <= n) {
    	// 空穴节点之最小孩子：开始时设为左孩子
        int child = hole << 1;

        // child 有右兄弟，且右兄弟比 child 还要小
        if (child != n && list.get(child + 1).compareTo(list.get(child)) < 0) {
            child++;
        }

        // 子节点比 e 要小，则子节点上升，空穴下降
        if (list.get(child).compareTo(e) < 0) {
            list.set(hole, list.get(child));
            hole = child;
        } else {
            break;
        }
    }

    list.set(hole, e);
}

构建堆

从最后一个内部节点（$\lfloor n/2 \rfloor$⌊n/2⌋）开始，依次对每个内部节点执行下滤操作：即，依次以每个内部节点为根，构建一棵最小二叉堆。

时间复杂度为 O(n) ：可以通过计算虚线的最大条数来得到。

// 构建堆
public void buildHeap(List<T> list) {
    this.list.clear();
    this.list.add(null);

    for (int i = 0; i < list.size(); i++) {
        this.list.add(list.get(i));
    }

    // 从最后一个内部节点开始，执行下滤操作
    for (int i = size() >> 1; i > 0; i--) {
        percolateDown(i);
    }
}