二叉堆和优先级队列

转自东哥labuladong的算法专栏，公众号”labuladong“

为了明白东哥算法秘籍里单链表解题套路，特地看下东哥的这篇文章。

二叉堆（Binary Heap）

性质比二叉搜索树（二叉排序树）还简单，两个主要操作 sink 和 swim，用以维护二叉堆的性质，主要应用也有两个【堆排序】和很有用的数据结构【优先级队列】

一、二叉堆概览

二叉堆和二叉树有啥关系？

二叉堆就是一颗特殊的二叉树（完全二叉树），只不过存储在数组里。一般的链表二叉树，我们操作结点的指针，而在数组里，我们把数组索引作为指针：

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

数组的第一个索引空着不用。

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

根据最大堆的性质，

数组元素arr[1]一定是所有元素中最大的元素。

二、优先级队列概览

实现一个简单的优先级队列，代码框架

public class MaxPQ
    extends Comparable> {
    // 存储元素的数组
    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

swim和sink操作都是为了维护堆结构。

因为在插入和删除元素时，可能会破坏最大堆或者最小堆的性质。

对于最大堆来说：

　　如果某个节点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);
    }
}

下沉代码实现

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

至此，明白了swim和sink操作就可以实现优先级队列了。

四、实现delMax和insert

这两个方法是建立在 swim 和 sink上的

insert 方法先把元素插入到堆底的最后（数组最后一个位置），然后再进行上浮到正确位置

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

delMax 方法先把堆顶元素A和堆底元素B对调 exch（pq[1], pq[N]），然后删除A，再将B下沉到正确位置

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

这里有个疑惑，max值应该还是pq[1]，但是思想是这么个思想。

至此，一个优先级队列就实现了，插入和删除元素的时间复杂度为O(logK),K为二叉堆（优先级队列）的元素总数。原因是，主要时间复杂度在于上浮和下沉操作，两者最多就是树（堆）的高度，就是log级别。

二叉堆和优先级队列

相关

标签