关于算法:二叉堆详解实现优先级队列

———–

二叉堆（Binary Heap）没什么神秘，性质比二叉搜寻树 BST 还简略。其次要操作就两个，sink（下沉）和 swim（上浮），用以保护二叉堆的性质。其次要利用有两个，首先是一种排序办法「堆排序」，第二是一种很有用的数据结构「优先级队列」。

本文就以实现优先级队列（Priority Queue）为例，通过图片和人类的语言来形容一下二叉堆怎么运作的。

首先，二叉堆和二叉树有啥关系呢，为什么人们总数把二叉堆画成一棵二叉树？

因为，二叉堆其实就是一种非凡的二叉树（齐全二叉树），只不过存储在数组里。个别的链表二叉树，咱们操作节点的指针，而在数组里，咱们把数组索引作为指针：

// 父节点的索引
int parent(int root) {return root / 2;}
// 左孩子的索引
int left(int root) {return root * 2;}
// 右孩子的索引
int right(int root) {return root * 2 + 1;}

画个图你立刻就能了解了，留神数组的第一个索引 0 空着不必，

PS：因为数组索引是数组，为了不便辨别，将字符作为数组元素。

你看到了，把 arr[1] 作为整棵树的根的话，每个节点的父节点和左右孩子的索引都能够通过简略的运算失去，这就是二叉堆设计的一个奇妙之处。为了不便解说，上面都会画的图都是二叉树构造，置信你能把树和数组对应起来。

二叉堆还分为最大堆和最小堆。最大堆的性质是：每个节点都大于等于它的两个子节点。相似的，最小堆的性质是：每个节点都小于等于它的子节点。

两种堆外围思路都是一样的，本文以最大堆为例解说。

对于一个最大堆，依据其性质，显然堆顶，也就是 arr[1] 肯定是所有元素中最大的元素。

优先级队列这种数据结构有一个很有用的性能，你插入或者删除元素的时候，元素会主动排序，这底层的原理就是二叉堆的操作。

数据结构的性能无非增删查该，优先级队列有两个次要 API，别离是 insert 插入一个元素和 delMax 删除最大元素（如果底层用最小堆，那么就是 delMin）。

上面咱们实现一个简化的优先级队列，先看下代码框架：

PS：为了清晰起见，这里用到 Java 的泛型，Key 能够是任何一种可比拟大小的数据类型，你能够认为它是 int、char 等。

public class MaxPQ
    <Key extends Comparable<Key>> {
    // 存储元素的数组
    private Key[] pq;
    // 以后 Priority Queue 中的元素个数
    private int N = 0;

    public MaxPQ(int cap) {
        // 索引 0 不必，所以多调配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    /* 返回以后队列中最大元素 */
    public Key max() {return pq[1];
    }

    /* 插入元素 e */
    public void insert(Key e) {...}

    /* 删除并返回以后队列中最大元素 */
    public Key delMax() {...}

    /* 上浮第 k 个元素，以保护最大堆性质 */
    private void swim(int k) {...}

    /* 下沉第 k 个元素，以保护最大堆性质 */
    private void sink(int k) {...}

    /* 替换数组的两个元素 */
    private void exch(int i, int j) {Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /* pq[i] 是否比 pq[j] 小？*/
    private boolean less(int i, int j) {return pq[i].compareTo(pq[j]) < 0;
    }

    /* 还有 left, right, parent 三个办法 */
}

空进去的四个办法是二叉堆和优先级队列的奥秘所在，上面用图文来一一了解。

为什么要有上浮 swim 和下沉 sink 的操作呢？为了保护堆构造。

咱们要讲的是最大堆，每个节点都比它的两个子节点大，然而在插入元素和删除元素时，不免毁坏堆的性质，这就须要通过这两个操作来复原堆的性质了。

对于最大堆，会毁坏堆性质的有有两种状况：

如果某个节点 A 比它的子节点（中的一个）小，那么 A 就不配做父节点，应该上来，上面那个更大的节点上来做父节点，这就是对 A 进行下沉。
如果某个节点 A 比它的父节点大，那么 A 不应该做子节点，应该把父节点换下来，本人去做父节点，这就是对 A 的上浮。

当然，错位的节点 A 可能要上浮（或下沉）很屡次，能力达到正确的地位，复原堆的性质。所以代码中必定有一个 while 循环。

仔细的读者兴许会问，这两个操作不是互逆吗，所以上浮的操作肯定能用下沉来实现，为什么我还要吃力写两个办法？

是的，操作是互逆等价的，然而最终咱们的操作只会在堆底和堆顶进行（等会讲起因），显然堆底的「错位」元素须要上浮，堆顶的「错位」元素须要下沉。

上浮的代码实现：

private void swim(int k) {
    // 如果浮到堆顶，就不能再上浮了
    while (k > 1 && less(parent(k), k)) {
        // 如果第 k 个元素比下层大
        // 将 k 换上去
        exch(parent(k), k);
        k = parent(k);
    }
}

画个 GIF 看一眼就明确了：

下沉的代码实现：

下沉比上浮稍微简单一点，因为上浮某个节点 A，只须要 A 和其父节点比拟大小即可；然而下沉某个节点 A，须要 A 和其 两个子节点 比拟大小，如果 A 不是最大的就须要调整地位，要把较大的那个子节点和 A 替换。

private void sink(int k) {
    // 如果沉到堆底，就沉不上来了
    while (left(k) <= N) {
        // 先假如右边节点较大
        int older = left(k);
        // 如果左边节点存在，比一下大小
        if (right(k) <= N && less(older, right(k)))
            older = right(k);
        // 结点 k 比俩孩子都大，就不用下沉了
        if (less(older, k)) break;
        // 否则，不合乎最大堆的构造，下沉 k 结点
        exch(k, older);
        k = older;
    }
}

画个 GIF 看下就明确了：

至此，二叉堆的次要操作就讲完了，一点都不难吧，代码加起来也就十行。明确了 sink 和 swim 的行为，上面就能够实现优先级队列了。

这两个办法就是建设在 swim 和 sink 上的。

insert 办法先把要插入的元素增加到堆底的最初，而后让其上浮到正确地位。

public void insert(Key e) {
    N++;
    // 先把新元素加到最初
    pq[N] = e;
    // 而后让它上浮到正确的地位
    swim(N);
}

delMax 办法先把堆顶元素 A 和堆底最初的元素 B 对调，而后删除 A，最初让 B 下沉到正确地位。

public Key delMax() {
    // 最大堆的堆顶就是最大元素
    Key max = pq[1];
    // 把这个最大元素换到最初，删除之
    exch(1, N);
    pq[N] = null;
    N--;
    // 让 pq[1] 下沉到正确地位
    sink(1);
    return max;
}

至此，一个优先级队列就实现了，插入和删除元素的工夫复杂度为 O(logK)，K 为以后二叉堆（优先级队列）中的元素总数。因为咱们工夫复杂度次要破费在 sink 或者 swim 上，而不论上浮还是下沉，最多也就树（堆）的高度，也就是 log 级别。

二叉堆就是一种齐全二叉树，所以适宜存储在数组中，而且二叉堆领有一些非凡性质。

二叉堆的操作很简略，次要就是上浮和下沉，来保护堆的性质（堆有序），外围代码也就十行。

优先级队列是基于二叉堆实现的，次要操作是插入和删除。插入是先插到最初，而后上浮到正确地位；删除是调换地位后再删除，而后下沉到正确地位。外围代码也就十行。

兴许这就是数据结构的威力，简略的操作就能实现奇妙的性能，真心拜服创造二叉堆算法的人！

关于算法:二叉堆详解实现优先级队列

一、二叉堆概览

二、优先级队列概览

三、实现 swim 和 sink

四、实现 delMax 和 insert

五、最初总结