java8集合框架(十)-Queue的实现类(PriorityQueue)

java8集合框架(十)-Queue的实现类(PriorityQueue)

前面完成了List的实现类,从这篇开始分析Queue的实现类。Queue是一种先进先出(FIFO)的数据结构,接口主要定义了入队列和出队列的签名。

Note:本篇源码分析基于jdk1.8版本

PriorityQueue

PriorityQueue是基于优先堆的无界队列实现。元素的优先顺序基于元素实现的Comparable接口或者构造函数中传入的Comparator比较器。对于前种情况,如元素并未实现该接口,会抛出异常ClassCastException。队列的头是优先级最高的元素,若多个元素优先级相同且都是最高,那么头元素是随机的。PriorityQueue不接受null值,非线程安全。

数据结构

PriorityQueue的核心数据结构是数组+堆。默认是最小堆,如队列元素为[1,2,3,4,5]时候,poll结果是1。可通过改变比较器实现最大堆。可以指定数组的初始大小。

1
2
3
4
5
6
7
8
//默认数组初始化大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//元素存放的数组容器,实现优先堆
transient Object[] queue;
//元素的个数
private int size = 0;
//比较器,可以通过构造函数传入
private final Comparator<? super E> comparator;

图片引用自http://www.cnblogs.com/yangecnu/archive/2014/03/02/3577568.html

初始化

1
2
3
4
5
6
7
8
9
10
11
12
public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null);}
public PriorityQueue(int initialCapacity) { this(initialCapacity, null); }
public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator);}
//构造函数
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
//根据作者的注释,这里的判断实际上是不需要的,仅为了兼容老版本的逻辑
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}

说明:PriorityQueue默认大小是11,可以在构造函数中传入comparator

入队列和出队列

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
//队尾插入元素,如果队列满无法插入,则抛异常
public boolean add(E e) {
return offer(e);
}
//队尾插入元素,如果队列满无法插入,则返回false
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
//扩容的条件是数组满
if (i >= queue.length)
grow(i + 1);
//size+1
size = i + 1;
//第一个元素简单处理,第二元素开始执行siftUp
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
//按优先级排序,从位置k向上筛
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
//从位置k将x元素上浮
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//"大于"父元素结束
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
//从队头删除元素,如果队列空,则抛异常
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
//从队头删除元素,如果队列空,则返回null
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
//最后一个元素从位置0下沉
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
//从位置k将x下沉
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
//下沉
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
//half是第一个叶子节点的位置,叶子节点没有下沉概念
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
//k的左儿子
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
//k的右儿子
int right = child + 1;
//取左右儿子较小的元素交换
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
//直至比左右儿子都小
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}

说明:用数组实现的二叉堆,入队列的元素不断上浮至大于其父元素,出队列的是堆顶元素,将最后一个元素从位置0下沉至小于其左右儿子元素。

offer图示

poll图示

图片引用自http://www.cnblogs.com/yangecnu/archive/2014/03/02/3577568.html

扩容

1
2
3
4
5
6
7
8
9
10
11
12
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 如果容量小于64则两倍扩容,否则1.5倍扩容
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//数组的复制,性能的消耗
queue = Arrays.copyOf(queue, newCapacity);
}

说明:当数组空间满,进行扩容。如果容量小于64则两倍扩容,否则1.5倍扩容。这里有数组的复制动作。

查看队首

1
2
3
4
5
6
7
8
9
10
11
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E peek() {
return (size == 0) ? null : (E) queue[0];
}

说明:堆顶是优先级最高的元素。

遍历

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
public Iterator<E> iterator() {
return new Itr();
}
private final class Itr implements Iterator<E> {
private int cursor = 0;
private int lastRet = -1;
private ArrayDeque<E> forgetMeNot = null;
private E lastRetElt = null;
private int expectedModCount = modCount;
public boolean hasNext() {
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
}
@SuppressWarnings("unchecked")
public E next() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
if (cursor < size)
return (E) queue[lastRet = cursor++];
if (forgetMeNot != null) {
lastRet = -1;
lastRetElt = forgetMeNot.poll();
if (lastRetElt != null)
return lastRetElt;
}
throw new NoSuchElementException();
}
public void remove() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
if (lastRet != -1) {
E moved = PriorityQueue.this.removeAt(lastRet);
lastRet = -1;
if (moved == null)
cursor--;
else {
//move是未被访问的元素
if (forgetMeNot == null)
forgetMeNot = new ArrayDeque<>();
forgetMeNot.add(moved);
}
} else if (lastRetElt != null) {
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw new IllegalStateException();
}
expectedModCount = modCount;
}
}
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}

说明:这里重点注意remove方法,该方法返回的非空值是未被访问但却因维护堆性质而被调到当前位置之前。将最后一个元素从当前位置可能做以下三种操作:

  • 成功下沉,该元素会在以后的某个时间被访问,返回null。
  • 成功上浮,则返回该元素,并将其添加到forgetMeNot,因为它并未被遍历,不要遗忘它。
  • 无需上浮或下沉,该元素会在下次调用next被访问。

总结

PriorityQueue是一种特殊的队列,可以按照优先级的高低排队。优先级高的元素会优先排在队列前面,不太公平但很符合现实情况。另外,优先队列的算法只能控制同一棵树父子之间的大小关系,不同树的元素大小是无法比较的。遍历的结果也没有顺序,可以通过Arrays.sort(queue.toArray(),comparator)达到有序遍历的目的。优先队列应用的典型场景有TopN问题(TopN小问题用大顶堆,TopN大问题用小顶堆)和堆排序等。

参考

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。