优先队列与堆-笔记

发表于 | 更新于 | 分类于 | | 阅读次数：
本文字数： 13k | 阅读时长 ≈ 12 分钟

引言

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将它们排序。很多情况下我们会先收集一些元素，处理当前键值最大的元素，然后再收集一些元素，再处理当前键值最大的元素，如此这般。例如，操作系统的进程调度、打印机中的打印任务调度等。

对于这些应用场景，一个合适的数据结构应该支持两种操作：删除最大/小元素、插入元素。这种数据结构叫做优先队列。

优先队列还可以作为算法设计工具用来构造其他算法，例如用来实现堆排序算法、以它为基础开发数据压缩算法、抽象若干重要的图搜索算法等等。

API

优先队列最重要的操作就是删除最大/小元素和插入元素。

MaxPQ(max priority queue) 的 API：

  • 构造器，此处省略了
  • void insert(Key v) 插入一个元素
  • Key max() 返回最大元素
  • Key delMax() 删除并返回最大元素
  • boolean isEmpty() 返回队列是否为空
  • int size() 返回优先队列中的元素个数

MinPQ 的 API 和 MaxPQ 类似，用 delMin() 替换 delMax() 就行了，也很容易实现。

初级实现

无序数组实现。要实现删除最大元素操作，先找到最大元素，将它和边界元素交换位置，然后删除边界元素。

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

protected Key[] items;
protected int n;

public void insert(Key v) {
    if (n == items.length) {
        resize(2 * items.length);
    }
    items[n++] = v;
}

public Key max() {
    if (isEmpty()) {
        throw new NoSuchElementException("ArrayMaxPQ underflow");
    }
    int posOfMax = posOfMax();
    return items[posOfMax];
}

public Key delMax() {
    if (isEmpty()) {
        throw new NoSuchElementException("ArrayMaxPQ underflow");
    }

    int posOfMax = posOfMax();
    exch(items, posOfMax, n-1);
    Key max = items[--n];
    items[n] = null;
    if (n > 0 && n == items.length/4) {
        resize(items.length/2);
    }
    return max;
}

private int posOfMax() {
    int posOfMax = 0;
    for (int i = 1; i < n; i++) {
        if (less((Comparable) items[posOfMax], (Comparable) items[i])) {
            posOfMax = i;
        }
    }
    return posOfMax;
}

protected void resize(int capacity) {
    assert capacity > n;
    Key[] temp = (Key[]) new Object[capacity];
    for (int i = 0; i < n; i++) {
        temp[i] = items[i];
    }
    items = temp;
}

有序数组实现。插入元素时，将较大元素向右移动一格以使数组保持有序（和插入排序一样）。

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

public void insert(Key v) {
    if (n == items.length) {
        resize(2 * items.length);
    }

    int i = n;
    for (; i > 0 && less((Comparable) v, (Comparable) items[i-1]); i--) {
        items[i] = items[i-1];
    }
    items[i] = v;
    n++;
}

public Key max() {
    if (isEmpty()) {
        throw new NoSuchElementException("ArrayMaxPQOrderly underflow");
    }
    return items[n-1];
}

public Key delMax() {
    if (isEmpty()) {
        throw new NoSuchElementException("ArrayMaxPQOrderly underflow");
    }
    Key max = items[--n];
    items[n] = null;
    if (n > 0 && n == items.length/4) {
        resize(items.length/2);
    }
    return max;
}

链表表示法也有两种：惰性方法，使用无序序列，删除时才找出最大元素；积极方法，使用有序序列，插入时就保持列表有序。下面是积极方法的实现：

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

private Node<Key> first;
private int n;

private static class Node<Key> {
    Key item;
    Node next;
}

public LinkListMaxPQ() {
    n = 0;
}

/**
 * 插入新元素, 并保持倒序排列
 * @param v
 */
public void insert(Key v) {
    Node<Key> newNode = new Node<Key>();
    newNode.item = v;

    Node<Key> prev = null;
    Node<Key> curr = first;
    while (curr != null && less((Comparable) v, (Comparable) curr.item)) {
        prev = curr;
        curr = curr.next;
    }
    if (prev == null) { // 队列为空或者新元素要排在 first 之前
        newNode.next = first;
        first = newNode;
    } else {
        newNode.next = prev.next;
        prev.next = newNode;
    }
    n++;
}

public Key max() {
    if (isEmpty()) {
        throw new NoSuchElementException("ArrayMaxPQ underflow");
    }
    return first.item;
}

public Key delMax() {
    if (isEmpty()) {
        throw new NoSuchElementException("ArrayMaxPQ underflow");
    }
    Key max = first.item;
    first = first.next;
    n--;
    return max;
}

基于堆的实现

什么是堆

首先，当堆(heap)这个词不加修饰地用在优先队列的上下文中时，一般都是指二叉堆这种数据结构。而二叉堆其实就是一棵二叉树，但它还有两个性质，结构性和堆序性(heap-order property)，这点和二叉查找树一样。简单起见，下文就把二叉堆叫做堆。

结构性

一棵二叉树，其元素总是从左到右层层填入（要么树被完全填满，要么就只有最底层未填满），这样的树被称为完全二叉树(complete binary tree)。堆就是一棵完全二叉树。一棵完全被填满的二叉树也被称为理想二叉树。

堆序性

当一棵二叉树的每个节点都大于等于它的两个子节点时，它被称为是堆有序的。 堆也是一棵堆有序的二叉树。

因此，二叉堆就是一棵堆有序的完全二叉树。 堆的操作可能会破坏两个性质中的一个，因此，堆的操作必须到其所有性质都被满足时才能终止。

如何表示堆

对于完全二叉树，可以将数组下标用作节点指针，这样就可以将其节点按照层次顺序放入数组中，根节点在位置 1，它的子节点在位置 2 和 3，而子节点的子节点则分别在位置 4、5、6 和 7，以此类推。位置规律：位置 k 的节点的父节点的位置为 $\lfloor k/2 \rfloor$，而它的两个子节点的位置分别为 2k 和 2k+1。注意，不使用数组的第一个位置，因为当 k=0 时，这条规律就跟实际情况冲突了！

注意，对于非完全二叉树，上述位置规律并不适用。我们倒是可以使用这个规律来验证一棵二叉树是否是完全二叉树。

将完全二叉树展现为树形结构时，就很容易理解下面两条结论：

  1. 一棵高为 h 的完全二叉树有 $2^h$ 到 $2^{h+1} - 1$ 个节点。注意，根节点的 h 为 0。
  2. 一棵大小为 N 的完全二叉树的高度为 $\lfloor lgN \rfloor$。

堆的操作

堆的操作会先打破堆的有序状态，然后再遍历堆并将其状态恢复，这个过程叫做堆的有序化(reheapifying)。

堆的有序化有两种情况：节点的键值增大或者在堆底插入一个新元素时，需要由下至上恢复堆的顺序；节点的键值减小或者根节点被替换为一个较小的元素时，需要由上至下恢复堆的顺序。由下至上的堆有序化叫做上浮(swim)或向上渗透(percolate up)，由上至下的堆有序化叫做下沉(sink)或向下渗透(percolate up)。

我们先看如何实现上浮、下沉这两个辅助操作，再看如何用这两个辅助操作实现插入、删除操作。

上浮操作(swim)

当某个节点比它的父节点更大时，该节点不断上浮，直到整个堆再次有序。有两种实现：

  1. 跟父节点比较，如果父节点小，就交换位置。重复该过程，直到遇到一个不小于它的父节点或到达堆的顶部
  2. 在下一个可用位置创建一个空位（针对插入新元素）或将键值变化的节点另存并将其所在位置置为空，然后检查 X 元素（即新元素或键值变化的元素）放在空位会不会破坏堆的序。如果不会，就将 X 元素放进空位，操作完成。否则，就将父节点的元素移入空位，这样空位就上浮至父节点所在位置，重复此过程，直到 X 能被放入空位为止。

第二种实现似曾相识，插入排序的一种优化方式就是将大于 X 的所有元素向后移动一格，然后直接插入。与不断交换的实现方式（第一种实现）相比，这种更高效，因为赋值操作更少了。

下沉操作(sink)

当某个节点比它的两个子节点或其中之一更小时，该节点不断下沉，直到整个堆再次有序。同样地，该操作也有两种实现，实现思想与上浮操作基本相同，这里不再啰嗦。注意边界条件测试，以及与较大的子节点进行比较即可。

插入元素

添加元素时，要从树顶向下一层一层从左向右填入新元素，这样才能确保添加新元素后它仍然是一棵完全二叉树，即保持了二叉树的结构性。对于数组表示形式来说，等价的描述就是将新元素添加到数组末尾，增加堆的大小并让新元素上浮到合适的位置。

删除最大/小元素

从数组顶端删除最大/小元素，并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。

构建堆(buildHeap)

两种实现：

  1. 逐个将输入元素插入到空优先队列。这种实现的运行时间与 $NlogN$ 成正比。
  2. 从右向左对前 1/2 的元素进行 sink 操作。之所以只扫描前 1/2，是因为对于二叉堆来说，至少有一半的节点是叶节点，具体证明请看 证明二叉堆至少有一半的节点是叶节点。用 sink 操作由 N 个元素构造堆只需少于 2N 次比较以及少于 N 次交换。

基于堆的优先队列

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

public class MaxPQ<Key> implements Iterable<Key> {

    private Key[] pq;                    // store items at indices 1 to n
    private int n;                       // number of items on priority queue
    private Comparator<Key> comparator;  // optional comparator

    public MaxPQ() {
        this(1);
    }

    public MaxPQ(int initCapacity) {
        this(initCapacity, null);
    }

    public MaxPQ(Comparator<Key> comparator) {
        this(1, comparator);
    }

    public MaxPQ(int initCapacity, Comparator comparator) {
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
        this.comparator = comparator;
    }

    public MaxPQ(Key[] keys) {
        n = keys.length;
        pq = (Key[]) new Object[keys.length + 1];
        for (int i = 0; i < n; i++) {
            pq[i + 1] = keys[i];
        }
        for (int k = n / 2; k >= 1; k--) {
            sink(k);
        }
        assert isMaxHeap();
    }

    // 跟父节点比较，如果父节点小，就交换位置。
    // 重复该过程，直到遇到一个不小于它的父节点或到达堆的顶部
    public void insert(Key x) {
        // double size of array if necessary
        if (n >= pq.length - 1) {
            resize(2 * pq.length);
        }

        // add x, and percolate it up to maintain heap invariant
        pq[++n] = x;
        swim(n);
        assert isMaxHeap();
    }

    // 在下一个可用位置创建一个空位, 然后检查 X 元素（即新元素）放在空位会不会破坏堆的序。
    // 如果不会，就将 X 元素放进空位，操作完成。否则，就将父节点的元素移入空位，
    // 这样空位就上浮至父节点所在位置，重复此过程，直到 X 能被放入空位为止。
    public void insert2(Key x) {
        // double size of array if necessary
        if (n >= pq.length - 1) {
            resize(2 * pq.length);
        }

        pq[++n] = x;
        int hole = n;
        percolateUp(hole);
        assert isMaxHeap();
    }

    public Key delMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("Priority queue underflow");
        }
        Key max = pq[1];
        pq[1] = pq[n--];
        pq[n + 1] = null; // to avoid loitering and help with garbage collection
        sink(1);
        if (n > 0 && (n == (pq.length - 1) / 4)) {
            resize(pq.length / 2);
        }
        assert isMaxHeap();
        return max;
    }

    public Key delMax2() {
        if (isEmpty()) {
            throw new NoSuchElementException("Priority queue underflow");
        }
        Key max = pq[1];
        pq[1] = pq[n--];
        pq[n+1] = null; // 防止对象游离
        percolateDown(1);
        if (n > 0 && (n == (pq.length - 1) / 4)) {
            resize(pq.length / 2);
        }
        assert isMaxHeap();
        return max;
    }

    public Key max() {
        if (isEmpty()) {
            throw new NoSuchElementException("Priority queue underflow");
        }
        return pq[1];
    }

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

    public int size() {
        return n;
    }

    // helper function to double the size of the heap array
    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }

    /*****************************************************
     * Helper functions to restore the heap invariant.
     *****************************************************/

    // 不断地交换元素位置
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k/2, k);
            k = k/2;
        }
    }

    // 不断地交换元素位置
    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            // j < n 等价于 j+1 <= n
            if (j < n && less(j, j+1)) { // 找出较大的, 而非较小的
                j++;
            }
            if (!less(k, j)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }

    // 不断地向下移动元素使空位向上渗透
    private void percolateUp(int hole) {
        Key x = pq[hole];
        while (hole > 1 && less(pq[hole/2], x)) {
            pq[hole] = pq[hole/2];
            hole = hole/2;
        }
        pq[hole] = x;
    }

    // 不断地向上移动元素使空位向下渗透
    private void percolateDown(int hole) {
        Key tmp = pq[hole];
        while (2*hole <= n) {
            int j = 2*hole;
            if ((j+1) <= n && less(j, j+1)) { // 找出较大的, 而非较小的
                j = j+1;
            }

            if (less(tmp, pq[j])) {
                pq[hole] = pq[j];
                hole = j;
            } else {
                break;
            }
        }
        pq[hole] = tmp;
    }

    /**********************************************
     * Helper functions for compares and swaps.
     **********************************************/

    private boolean less(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
        } else {
            return comparator.compare(pq[i], pq[j]) < 0;
        }
    }

    private boolean less(Key key1, Key key2) {
        if (comparator == null) {
            return ((Comparable<Key>) key1).compareTo(key2) < 0;
        } else {
            return comparator.compare(key1, key1) < 0;
        }
    }

    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }

    // is pq[1..N] a max heap?
    private boolean isMaxHeap() {
        return isMaxHeap(1);
    }

    // is subtree of pq[1..n] rooted at k a max heap?
    private boolean isMaxHeap(int k) {
        if (k > n) return true;
        int left = 2 * k;
        int right = 2 * k + 1;
        if (left <= n && less(k, left)) return false;
        if (right <= n && less(k, right)) return false;
        return isMaxHeap(left) && isMaxHeap(right);
    }

}

算法性能评估

对于一个含有 N 个元素的基于堆的优先队列，插入元素操作只需不超过 $(lgN+1)$ 次比较，删除最大元素操作需要不超过 $2lgN$ 次比较。

优先队列的各种实现在最坏情况下运行时间的增长数量级

数据结构 插入元素 删除最大元素
有序数组 N 1
无序数组 1 N
堆 $logN$ $logN$
理想情况 1 1

参考资源

《算法（第四版）》Robert Sedgewick 等著，第 2 章-排序
《数据结构与算法分析-Java语言描述》Mark Allen Weiss 著，第 6 章-优先队列（堆）

0%