什么是优先队列?

在平常的工作当中,我们可能会遇到需要处理有序的元素的场景,但我们往往并不要求这些元素全部有序,或者我们并不想一次性将这些元素排序。很多情况下我们是先收集到一些元素,处理当前最大的元素,然后再收集更多的元素,再处理当前最大的元素。
例如,我们在我们的应用程序中为其中的事件分配一个优先级,并且总是要处理下一个优先级最高的事件。
在这种情况下,一个合适的数据结构应该支持这两种操作:删除最大元素插入元素。这种数据结构叫优先队列。

API

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

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
package net.sunzhenyu.miscellaneous.dsa.priority_queue;

/**
* Priority Queue interface
*
* @author <a href="mailto:sunzhenyucn@gmail.com">SunZhenyu</a>
* @version 0.0.1
* @date 2018/05/30
* @since 1.8
*/
public interface IPriorityQueue<T extends Comparable<T>> {

/**
* Insert specified element to queue
*
* @param element Specified element
*/
void insert(T element);

/**
* Get the max element
*
* @return Max element
*/
T max();

/**
* Delete the max element and return
*
* @return deleted element
*/
T deleteMax();

/**
* If current queue is empty, return {@code true}
*
* @return If current queue is empty, return {@code true}
*/
boolean isEmpty();

/**
* Get current queue's elements count
*
* @return Current queue's elements count
*/
int size();
}

基础实现(使用数组或者链表)

我们先来考虑两种最简单的实现,使用数组或者链表。

  1. 我们先来看下无序数组的实现,在这里我们可以用之前写的栈这种数据结构的代码,\(insert()\)方法和\(push()\)方法完全一样,我们如果需要删除最大的元素,则在\(pop()\)方法上动手脚,可以在其中添加一段类似于选择排序的内循环,来找出最大元素并将其和边界元素交换然后删除它。

    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
    package net.sunzhenyu.miscellaneous.dsa.priority_queue;

    @SuppressWarnings("unchecked")
    public class DisorderlyArrayPQ<T extends Comparable<T>> implements IPriorityQueue<T> {

    private static final Integer DEFAULT_INITIAL_CAPACITY = 15;
    private T[] elements;
    private int size;

    public DisorderlyArrayPQ() {
    this(DEFAULT_INITIAL_CAPACITY);
    }

    public DisorderlyArrayPQ(int initialCapacity) {
    if (!(initialCapacity > 0 & initialCapacity > DEFAULT_INITIAL_CAPACITY)) {
    this.elements = (T[]) new Comparable[DEFAULT_INITIAL_CAPACITY];
    } else {
    this.elements = (T[]) new Comparable[initialCapacity];
    }
    }

    //TODO: Constructor with array

    private void ensureCapacity() {
    if (this.elements.length >= size) {
    expand(this.elements.length << 1);
    }
    }

    private void expand(int newCapacity) {
    T[] newArr = (T[]) new Comparable[newCapacity];
    System.arraycopy(this.elements, 0, newArr, 0, size);
    this.elements = newArr;
    }

    private T findMax(boolean removed) {
    int maxIndex = 0;
    for (int i = 0; i < size; i++) {
    if (less(maxIndex, i)) {
    maxIndex = i;
    }
    }
    T oldElement = this.elements[maxIndex];
    if (removed) {
    exchange(maxIndex, size - 1);
    remove(maxIndex);
    }
    return oldElement;
    }

    private void remove(int index) {
    this.elements[index] = null;
    size--;
    }

    @Override
    public void insert(T element) {
    ensureCapacity();
    this.elements[size++] = element;
    }

    @Override
    public T max() {
    return findMax(false);
    }

    @Override
    public T deleteMax() {
    return findMax(true);
    }

    @Override
    public boolean isEmpty() {
    return this.size > 0;
    }

    @Override
    public int size() {
    return this.size;
    }

    private boolean less(int i, int j) {
    return this.elements[i].compareTo(this.elements[j]) < 0;
    }

    private void exchange(int i, int j) {
    T swap = this.elements[i];
    this.elements[j] = this.elements[i];
    this.elements[i] = swap;
    }
    }
  2. 接下来我们再来看下有序数组的实现,这种和无序数组的实现不同,我们在\(insert()\)方法中动手脚,我们在插入元素的时候将所有最大的元素向右移动一格使得数组保持有序,这样,最大的元素总会在数组的一边,那么我们就不需要在\(pop()\)方法上进行更改了。

    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
    package net.sunzhenyu.miscellaneous.dsa.priority_queue;

    @SuppressWarnings("unchecked")
    public class OrderlyArrayPQ<T extends Comparable<T>> implements IPriorityQueue<T> {

    private static final Integer DEFAULT_INITIAL_CAPACITY = 15;
    private T[] elements;
    private int size;

    public OrderlyArrayPQ() {
    this(DEFAULT_INITIAL_CAPACITY);
    }

    public OrderlyArrayPQ(int initialCapacity) {
    if (initialCapacity > 0 & initialCapacity > DEFAULT_INITIAL_CAPACITY) {
    this.elements = (T[]) new Comparable[initialCapacity];
    } else {
    this.elements = (T[]) new Comparable[DEFAULT_INITIAL_CAPACITY];
    }
    this.size = 0;
    }

    private void ensureCapacity() {
    if (this.elements.length >= size) {
    expand(this.elements.length << 1);
    }
    }

    private void expand(int newCapacity) {
    T[] newArr = (T[]) new Comparable[newCapacity];
    System.arraycopy(this.elements, 0, newArr, 0, size);
    this.elements = newArr;
    }

    private boolean less(T i, T j) {
    return i.compareTo(j) < 0;
    }

    @Override
    public void insert(T element) {
    ensureCapacity();
    int index = this.size - 1;
    while (index >= 0 && less(element, this.elements[index])) {
    this.elements[index + 1] = this.elements[index];
    index--;
    }
    this.elements[index + 1] = element;
    size++;
    }

    @Override
    public T max() {
    int index = size;
    return this.elements[--index];
    }

    @Override
    public T deleteMax() {
    int index = --size;
    T oldElement = this.elements[index];
    this.elements[index] = null;
    return oldElement;
    }

    @Override
    public boolean isEmpty() {
    return this.size > 0;
    }

    @Override
    public int size() {
    return this.size;
    }
    }

基于二叉堆(Binary Heap)的实现

二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级存储(不使用数组的第一个下标索引)。
用二叉堆实现的具体方法就是将二叉树的节点按照层级顺序放入数组,根节点在下标\(1\),它的子节点在下标\(2\)和\(3\),它的子节点的子节点的位置分别在\(4\)、\(5\)、\(6\)和\(7\)。以此类推。
pq-tree-1
在一个二叉堆中,位置\(k\)的节点的父节点的位置为\(k \div 2\),而它的两个子节点的位置分别为\(k \times 2\)和\(k \times 2 + 1\),通过这样不使用下标指针的情况下,我们可以通过计算数组下标索引在树中上下移动:从\(a[k]\)向上一层移动就使\(k\)等于\(k \div 2\),向下移动一层就使\(k\)等于\(k \times 2\)或者\(k \times 2 + 1\)。
pq-tree-2
表示一个大小为\(N\)的二叉堆,我们不使用\(elements[0]\),堆元素放在\(elements[1]\)至\(elements[N]\)中,我们主要通过以下两个函数来访问元素:\(less()\)和\(exchange()\),我们对堆的操作首先会进行一些简单的改动,打破堆的状态,然后再遍历堆并按照要求将堆恢复成正确的状态,这个过程叫做堆的有序化(Reheapifying)

1
2
3
4
5
6
7
8
9
private boolean less(int i, int j) {
return this.elements[i].compareTo(this.elements[j]) < 0;
}

private void exchange(int i, int j) {
T oldElement = this.elements[i];
this.elements[i] = this.elements[j];
this.elements[j] = oldElement;
}

在有序化的过程中我们会遇到两种情况,当某个节点的优先级上升,我们需要由下至上的恢复堆的顺序,当某个节点的优先级下降,我们需要由上至下的恢复堆的顺序。我们实现了这两种辅助操作,实现插入元素与删除最大元素的操作就会非常简单。

由下至上的堆有序化

如果堆的有序状态因为某个节点比它的父节点更大而打破了这种状态,那么我们就需要通过它和它的父节点进行交换来修复,我们将通过位置\(k\)的节点的父节点\(k \div 2\)这种规则来寻找父节点。交换之后,这个节点比它的两个子节点都要大(这两个子节点一个是曾经的父节点,另一个是曾经父节点的子节点),但是目前的父节点仍可能比它现在的父节点还要大,那么我们就要继续按照之前的规则继续进行交换直到堆恢复有序状态。

1
2
3
4
5
6
private void swim(int index) {
while (index > 1 && less(index >> 1, index)) {
exchange(index >> 1, index);
index >>= 1;
}
}

由上至下的堆有序化

如果堆有序化状态应为某个父节点比其子节点们或者是子节点们的其中之一更小而打破了,那么我们就应该通过将它和它的子节点中较大者来进行交换来汇付堆的有序化状态,但是“牵一发而动全身”,有可能其他节点也会受到影响,所以我们需要不断地使用相同的方式来将整个堆的有序化状态恢复。关于父节点\(k\)的两个子节点我们可以用\(k \times 2\)和\(k \times 2 + 1\)来找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
private void sink(int index) {
while (2 * index <= size) {
int temp = 2 * index;
if (temp < size && less(temp, temp + 1)) {
temp++;
}
if (!less(index, temp)) {
break;
}
exchange(index, temp);
index = 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
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
package net.sunzhenyu.miscellaneous.dsa.priority_queue;

@SuppressWarnings("unchecked")
public class BinaryHeapPriorityQueue<T extends Comparable<T>> implements IPriorityQueue<T> {

private T[] elements;
private int size;
private static final Integer DEFAULT_CAPACITY = 15;

public BinaryHeapPriorityQueue() {
this(DEFAULT_CAPACITY);
}

public BinaryHeapPriorityQueue(int initialCapacity) {
if (initialCapacity > 0 && initialCapacity > DEFAULT_CAPACITY) {
this.elements = (T[]) new Comparable[initialCapacity];
} else {
this.elements = (T[]) new Comparable[DEFAULT_CAPACITY];
}
this.size = 0;
}

private boolean less(int i, int j) {
return this.elements[i].compareTo(this.elements[j]) < 0;
}

private void exchange(int i, int j) {
T oldElement = this.elements[i];
this.elements[i] = this.elements[j];
this.elements[j] = oldElement;
}

private void swim(int index) {
while (index > 1 && less(index >> 1, index)) {
exchange(index >> 1, index);
index >>= 1;
}
}

private void sink(int index) {
while (2 * index <= size) {
int temp = 2 * index;
if (temp < size && less(temp, temp + 1)) {
temp++;
}
if (!less(index, temp)) {
break;
}
exchange(index, temp);
index = temp;
}
}

private void ensureCapacity() {
if (this.elements.length - 1 == size) {
expand(this.elements.length << 1);
}
}

private void expand(int newCapacity) {
T[] newArr = (T[]) new Comparable[newCapacity];
System.arraycopy(this.elements, 1, newArr, 1, size);
this.elements = newArr;
}

private void ensureNonNull(T element) {
if (element == null) {
throw new NullPointerException("Specified element cannot be null");
}
}

@Override
public void insert(T element) {
ensureNonNull(element);
ensureCapacity();
this.elements[++size] = element;
swim(size);
}

private T findMax(boolean removed) {
T maxElement = this.elements[1];
if (removed) {
exchange(1, size--);
this.elements[size + 1] = null;
sink(1);
}
return maxElement;
}

@Override
public T max() {
return findMax(false);
}

@Override
public T deleteMax() {
return findMax(true);
}

@Override
public boolean isEmpty() {
return this.size == 0;
}

@Override
public int size() {
return this.size;
}
}

基于多叉堆的实现

我们可以基于\(d\)叉树来构建\(d\)叉堆,譬如我们如果要用数组来表示一个由完全三叉树构造的一个三叉堆,对于数组中\(1 \backsim N\)的\(N\)个元素,位置为\(k\)的父节点,它的三个子节点的位置分别为:\(k \times 3 - 1\)、\(k \times 3\)、\(k \times 3 + 1\)。

索引优先队列

使用二叉堆实现的优先队列有一个缺点,就是不能直接访问已经存在于队列中的元素,并且更新它们。我们可以基于优先队列实现一种可以对优先队列中已经存在的元素进行直接访问的一种数据结构,我们可以维护每个在队列里面的元素的下标索引,通过索引来进行对队列内元素的直接访问。
然而仅仅维护队列内元素的下标索引是不够的,每次我们去查找某个元素的时候,都需要将维护着下标索引的数组进行遍历。
现在我们假设有两个数组,分别名为:\(element[]\)和\(pq[]\),\(element[]\)中存放的是已知的存在于队列中的元素,\(pq[]\)中存放的是这些元素在\(element[]\)数组中的下标索引,为了能够快速找到\(pq[]\)中存放的\(element[]\)数组中对应的下标索引,我们需要额外的去维护一个数组\(qp[]\),这里面存储的是\(element[]\)数组中对应的下标索引存放在\(pq[]\)中的对应下标。

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
package net.sunzhenyu.miscellaneous.dsa.priority_queue;

import java.util.Arrays;
import java.util.NoSuchElementException;

public class IndexMinPQ<T extends Comparable<T>> implements IIndexPriorityQueue<T> {

private int max;
private int size;
private int[] pq;
private int[] qp;
private T[] elements;

@SuppressWarnings("unchecked")
public IndexMinPQ(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Initial capacity cannot smaller than zero.");
}
size = 0;
max = initialCapacity;
elements = (T[]) new Comparable[initialCapacity + 1];
pq = new int[initialCapacity + 1];
qp = new int[initialCapacity + 1];
Arrays.fill(qp, -1);
}

@Override
public void insert(int index, T element) {
ensureMax(index);
if (contains(index)) {
throw new IllegalArgumentException("Index is already in the priority queue.");
}
size++;
qp[index] = size;
pq[size] = index;
elements[index] = element;
swim(size);
}

@Override
public void change(int index, T element) {
ensureMax(index);
if (!contains(index)) {
throw new IllegalArgumentException("Index is not in the priority queue.");
}
elements[index] = element;
swim(qp[index]);
sink(qp[index]);
}

@Override
public boolean contains(int index) {
ensureMax(index);
return qp[index] != -1;
}

@Override
public void delete(int index) {
ensureMax(index);
if (!contains(index)) {
throw new IllegalArgumentException("Index is not in the priority queue.");
}
int i = qp[index];
exchange(i, size--);
swim(i);
sink(i);
elements[i] = null;
qp[i] = -1;
}

@Override
public T min() {
ensureUnderflow();
return elements[pq[1]];
}

@Override
public int minIndex() {
ensureUnderflow();
return pq[1];
}

@Override
public int deleteMin() {
ensureUnderflow();
int min = pq[1];
exchange(1, size--);
sink(1);
assert min == pq[size + 1];
qp[min] = -1;
elements[min] = null;
pq[size + 1] = -1;
return min;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public int size() {
return size;
}

private void ensureMax(int index) {
if (index < 0 || index >= max) {
throw new IllegalArgumentException("Index cannot bigger than " + max);
}
}

private void ensureUnderflow() {
if (size == 0) {
throw new NoSuchElementException("Priority queue underflow.");
}
}

private boolean greater(int i, int j) {
return elements[pq[i]].compareTo(elements[pq[j]]) > 0;
}

private void exchange(int i, int j) {
int oldElementIndex = pq[i];
pq[i] = pq[j];
pq[j] = oldElementIndex;
qp[pq[i]] = i;
qp[pq[j]] = j;
}

private void swim(int index) {
while (index > 1 && greater(index / 2, index)) {
exchange(index, index / 2);
index /= 2;
}
}

private void sink(int index) {
while (2 * index <= size) {
int temp = 2 * index;
if (temp < size && greater(temp, temp + 1)) {
temp++;
}
if (!greater(index, temp)) {
break;
}
exchange(index, temp);
index = temp;
}
}
}