算法-二叉堆及优先级队列

二叉堆简介

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

因为，二叉堆在逻辑上其实是一种特殊的二叉树（完全二叉树），只不过存储在数组里。一般的链表二叉树，我们操作节点的指针，而在数组里，我们把数组索引作为指针：

// 父节点的索引
int parent(int root) {
    return root / 2;
}
// 左孩子的索引
int left(int root) {
    return root * 2;
}
// 右孩子的索引
int right(int root) {
    return root * 2 + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

因为这棵二叉树是「完全二叉树」，所以把 arr[1] 作为整棵树的根的话，每个节点的父节点和左右孩子的索引都可以通过简单的运算得到，这就是二叉堆设计的一个巧妙之处。

优先级队列简介

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

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

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

这里用到 Java 的泛型，Key 可以是任何一种可比较大小的数据类型，比如 Integer 等类型。

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

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

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

    /* 插入元素 e */
    //insert 方法先把要插入的元素添加到堆底的最后，然后让其上浮到正确位置。
    public void insert(Key e) {
	    size++;
	    // 先把新元素加到最后
	    pq[size] = e;
	    // 然后让它上浮到正确的位置
	    swim(size);
	}

    /* 删除并返回当前队列中最大元素 */
    //delMax 方法先把堆顶元素 A 和堆底最后的元素 B 对调，然后删除 A，最后让 B 下沉到正确位置。
    public Key delMax() {
	    // 最大堆的堆顶就是最大元素
	    Key max = pq[1];
	    // 把这个最大元素换到最后，删除之
	    swap(1, size);
	    pq[size] = null;
	    size--;
	    // 让 pq[1] 下沉到正确位置
	    sink(1);
	    return max;
	}

    /* 上浮第 x 个元素，以维护最大堆性质 */
   private void swim(int x) {
	    // 如果浮到堆顶，就不能再上浮了
	    while (x > 1 && less(parent(x), x)) {
	        // 如果第 x 个元素比上层大
	        // 将 x 换上去
	        swap(parent(x), x);
	        x = parent(x);
	    }
	}

    /* 下沉第 x 个元素，以维护最大堆性质 */
    private void sink(int x) {
	    // 如果沉到堆底，就沉不下去了
	    while (left(x) <= size) {
	        // 先假设左边节点较大
	        int max = left(x);
	        // 如果右边节点存在，比一下大小
	        if (right(x) <= size && less(max, right(x)))
	            max = right(x);
	        // 结点 x 比俩孩子都大，就不必下沉了
	        if (less(max, x)) break;
	        // 否则，不符合最大堆的结构，下沉 x 结点
	        swap(x, max);
	        x = max;
	    }
	}

    /* 交换数组的两个元素 */
    private void swap(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 三个方法 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

插入和删除元素的时间复杂度为 O(logK)，K 为当前二叉堆（优先级队列）中的元素总数。因为我们时间复杂度主要花费在 sink 或者 swim 上，而不管上浮还是下沉，最多也就树（堆）的高度，也就是 log 级别。

注意事项

1. 什么时候使用swim，什么时候使用sink？ swim为上浮操作，当底层元素有错位时调用,sink为下沉操作，当顶层元素有错位时调用

最后总结

二叉堆就是一种完全二叉树，所以适合存储在数组中，而且二叉堆拥有一些特殊性质。

二叉堆的操作很简单，主要就是上浮和下沉，来维护堆的性质（堆有序），核心代码也就十行。

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