关于数据结构中的堆（heap）

注，这里的堆指的都是二叉堆。

什么是堆

可以认为，堆是这样一种二叉树，它的每一个节点的值都大于（或小于）其两个子节点的值。前者称为大根堆，或大顶堆，后者称为小根堆，或小顶堆。

堆很容易用完全二叉树来表示，因而使用数组模拟堆是合理的。可以用这样的数组来模拟堆——它从 1 开始计数，对每一个节点 i，其左子结点为 i*2，其右节点为 i*2+1，其父节点为 i/2。树的根节点为 1。

堆对解决诸如找到数组的前 k 大（小）的元素这样的问题是极其合适的。对于找到前 K 大的元素这个问题，可以构造一个小顶堆，对数组中每一个元素，如果其大于小顶堆的顶（这说明该元素大于已经找到的元素的最小值），则更新堆。遍历完成后堆中元素就为前 K 大的元素。

堆也被用作构造优先队列（Priority Queue）。这种队列有着这样的性质——它能在 O(log n) 时间内取出最小（最大）元素，在 O(log n) 时间内插入元素。下面给出优先队列的实现。

堆的一般方法

一般的堆有两个方法，swim(int):void和sink(int):void。它们分别是将元素上浮和下沉。

swim 方法

swim 方法表示将一个元素更新（或插入）后上浮。

可以想象这样一个场景——一个黑社会里新来了一个人，他能力比他的领导强，因而抢了领导的位置，领导变成了他的下属。这个过程一直循环，直到他的上司比他强为止，或者（当然，也可能根本进不去循环，他就是最菜的 w）。当然，这里的“强”如何区分取决于堆是大顶堆还是小顶堆。

下面给出其实现——

void swim (int k) { // 这里的 k 给的是数组的下标
    while (k > 1 && stronger(arr[k], arr[k / 2])) { // 当 k 还没到根节点，且 k 比它的父节点“强”
        exch(arr, k, k / 2);
        k = k / 2;
    }
}

sink 方法

sink 方法表示将一个元素下沉。一个通常的应用是，删除了堆顶，然后将堆尾元素置于堆顶并调用 sink(1)，使其置于合适位置。

可以想象这样一个场景——一个领导退休了，空降了个乐色，他的位置被下面的人顶掉（这是黑社会，不是阶级社会：-) ），他就成为了这个“下面的人”的下属，这个过程一直循环，直到他比他的下属都强为止。

要注意的是，他应当是被下面的两个人中比较“强”的那个顶掉，因为如果是被弱的顶掉，这个弱的也会被再顶掉（不满足堆的性质了）。

下面给出实现——

void sink(int k) {
    while (k * 2 < arr.size()) { // 如果他还有下级的话 w
        // 这里找出 k 的两个子节点中更“强”的哪一个
        int i = k * 2;
        if (i + 1 < arr.size() && stronger(arr[i + 1], arr[i])) i++;
        
        exch (arr, i, k);
        k = i;
    }
}

优先队列的实现

下面实现优先队列。其接受一个或两个参数——堆的长度和 Comparator。优先队列主要需要实现两个方法——removeTop 方法和 insert 方法，前者移除堆顶元素，将堆尾元素移到堆顶并调用 sink 方法，后者插入元素到堆尾并调用 swim 方法。

public class PQ<T extends Comparable<T>> {
    private Comparator<T> comparator;
    private T[] arr;
    int n = 0; // 指向堆的最后一个元素

    public PQ(int n) { // 这里的 n 是堆的最大大小
        arr = (T[]) new Comparable[n + 1];
        comparator = (i, j) -> i.compareTo(j); // 默认为构造小顶堆
    };

    public PQ(int n, Comparator<T> comparator) {
        this(n);
        this.comparator = comparator;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }

    public void insert(T t) {
        arr[++n] = t;
        swim(n);
    }

    public T removeTop() {
        exch(1, n);
        T temp = arr[n];
        arr[n--] = null;
        sink(1);
        return temp;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("PQ[");
        for (int i = 1; i <= n; i++)
            res.append(arr[i] + (i == n ? "" : ", "));
        res.append("] size=" + (arr.length - 1));
        return res.toString();
    }

    private void swim(int k) { // 这里的 k 给的是数组的下标
        while (k > 1 && stronger(k, k / 2)) { // 当 k 还没到根节点，且 k 比它的父节点“强”
            exch(k, k / 2);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (k * 2 <= n) { // 如果他还有下级的话 w
            // 这里找出 k 的两个子节点中更“强”的哪一个
            int i = k * 2;
            if (i + 1 <= n && stronger(i + 1, i))
                i++;
            if (!stronger(i, k))
                return; // 如果 i 不比 k 强
            exch(i, k);
            k = i;
        }
    }

    private void exch(int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private boolean stronger(int i, int j) {
        return comparator.compare(arr[i], arr[j]) < 0;
    }
}

找到数组前 k 小的元素

对于 这一题，要找到数组的前 k 小的元素，则需要维护一个大小为 k 的大顶堆，其中元素代表当前找到的 k 个最小元素，然后遍历数组，如果找到的数小于大顶堆中最大的数，则更新堆，否则不做动作。这里只需要更改一下 insert 方法。

void insert(int i) { // 将 i 插入到堆中
    if (!isFull()) { // 如果堆未满
        arr[++p] = i;
        swim(p);
    }
    else if (i < arr[1]) {
        arr[1] = i;
        sink(1);
    }
}