PriorityQueue 源码分析

结构体系

1
2
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

PriorityQueue是通过最小堆（？）实现内部元素按一定顺序的队列，也称其为优先队列。从结构体系上看，PriorityQueue是继承自AbstractQueue的，即PriorityQueue实现了基本的队列的操作。但为何PriorityQueue能够实现元素按指定排序存在队列呢，那么我们应该看它的成员变量部分。

若忘了最大/小堆的概念，可以查看这篇文章堆排序（Heap Sort）

常量与重要的成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 默认容器初始大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;

// 容器最大大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// PriorityQueue 真实操作容器(知道最大/小堆性质的，应该不难明白)
transient Object[] queue;

// 记录容器内部实际元素个数
private int size = 0;

/**
  * The comparator, or null if priority queue uses elements'
  * natural ordering.
  */
// 上述注释表明comparator若为空时，即使用自然递增的顺序存储元素
// 那么既然给出了这个comparator，就说明了该comparator可以由用户给定
private final Comparator<? super E> comparator;

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
}

// 关键构造函数，这一步证实了可以由用户传递自定义的comparator来实现自定义顺序容器
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
  	if (initialCapacity < 1)
    	throw new IllegalArgumentException();
  	this.queue = new Object[initialCapacity];
  	this.comparator = comparator;
}

增加操作 —— add()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean add(E e) {
  	return offer(e);
}

public boolean offer(E e) {
    if (e == null)
      	throw new NullPointerException();
    modCount++;
    int i = size;
  	// 保证容器能够存储所有元素
    if (i >= queue.length)
      	grow(i + 1);
    size = i + 1;
    if (i == 0)
      	queue[0] = e;
    else
      	// 实际操作部分
      	siftUp(i, e);
    return true;
}

关键部分如下所示：

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
// 这一步就是PriorityQueue的关键部分
private void siftUp(int k, E x) {
  	// 若comparator不为空，则使用用户给定的comparator，否则则使用元素本身提供的比较器
    if (comparator != null)
      	siftUpUsingComparator(k, x);
    else
      	siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
// comparator为空时调用
private void siftUpComparable(int k, E x) {
  	// 获取元素本身，并转化为可Comparable类型
    Comparable<? super E> key = (Comparable<? super E>) x;
  	// 若k>0，即k未处于根元素位置
    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;
}

@SuppressWarnings("unchecked")
// comparator不为空时调用
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
      	int parent = (k - 1) >>> 1;
      	Object e = queue[parent];
      	// 使用用户给定的comparator
      	if (comparator.compare(x, (E) e) >= 0)
        	break;
      	queue[k] = e;
      	k = parent;
    }
    queue[k] = x;
}

删除操作 - poll()

1
2
3
4
5
6
7
8
9
10
11
12
public E poll() {
    if (size == 0)
      	return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
      	siftDown(0, x);
    return result;
}

与add()同理。

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
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        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;
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

查找操作 - peek()

1
2
3
4
// 时间复杂度O(1)
public E peek() {
  	return (size == 0) ? null : (E) queue[0];
}