## PriorityQueue源码分析 原

Hosee

PriorityQueue是从JDK1.5开始提供的新的数据结构接口，它是一种基于 优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列，也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）

## 建堆：

PriorityQueue内部的数组声明如下：

``````private static final int DEFAULT_INITIAL_CAPACITY = 11;

/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d.  The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
private transient Object[] queue;``````

PriorityQueue的默认长度为11，而且PriorityQueue是会扩容的

``````/**
* Increases the capacity of the array.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
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);``````

PriorityQueue初始化过程和最大堆的建堆过程基本上一样的(想了解建堆过程请查看排序篇的堆排)，从有子节点的最靠后元素开始往前，每次都调用siftDown方法来调整。这个过程也叫做heapify。

``````/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified collection.  If the specified collection is an instance of
* a {@link SortedSet} or is another {@code PriorityQueue}, this
* priority queue will be ordered according to the same ordering.
* Otherwise, this priority queue will be ordered according to the
* {@linkplain Comparable natural ordering} of its elements.
*
* @param  c the collection whose elements are to be placed
*         into this priority queue
* @throws ClassCastException if elements of the specified collection
*         cannot be compared to one another according to the priority
*         queue's ordering
* @throws NullPointerException if the specified collection or any
*         of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}``````
PriorityQueue支持将Collection类型直接转成 PriorityQueue。

``````private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}

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;
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;
}

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;
}``````

``````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. 此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue 类。

2. 此实现为offer、poll、和 add 方法提供 O(logn) 时间；为 remove(Object) 和 contains(Object) 方法提供O(n)时间；为检索方法（peek、element 和 size）提供O(1)。

3. 方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。因为最小堆只能保证根结点是最小，不能保证整体都有序。

## Reference：

1. http://cuisuqiang.iteye.com/blog/2019157

2. http://shmilyaw-hotmail-com.iteye.com/blog/1827136

### 评论(0)

Java集合--Queue(Java中实现1)

1.2 Java中的实现 上一篇，阐述了队列的实现结构，通过图片的形式让大家有了更进一步的了解。 接下来，我，我们来看看队列在Java具体是如何成仙了，来看下Queue的代码！！！ 在Java中，Array...

2017/10/21
0
0

2019/05/02
32
0

woshixin
2018/10/10
24
0
《k8s-1.13版本源码分析》-抢占调度

CloudGeek
2019/03/29
0
0
Java 优先队列 PriorityQueue PriorityBlockingQueue 源码分析

2019/01/04
0
0

pygame---2048

ivyhaha

11
0

24
0
Java并发编程(03)：多线程并发访问，同步控制

27
0
MyBatis-Spring:整合Mybatis与Spring方式二:SqlSessionDaoSupport

141
0
count(1)、count(*)与count(列名)的执行区别

16
0