优先级队列PriorityQueue源码分析
优先级队列是一种抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆(数据结构)来实现。
初级实现
有许多简单低效的实现。如用一个有序的数组；或使用无序数组，在每次取出时搜索全集合，这种方法插入的效率为O(1)，但取出时效率为O(n)。
典型实现
出于性能考虑，优先队列用堆 (数据结构)来实现，具有O(log n)时间复杂度的插入元素性能，O(n)的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为O(log n)，构造二叉树的时间复杂度为O(n log n)。
Collection家族关系图
源码分析
继承关系
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable
无参构造函数
private static final int DEFAULT_INITIAL_CAPACITY = 11;
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
transient Object[] queue;
private final Comparator<? super E> comparator;
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
无参构造调用了int和Comparator参数的构造方法，可以看到PriorityQueue底层是一个Object[],默认初始容量是11，比较器默认为空，自然排序。
Collection参数构造
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);
}
}
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (Object e : a)
if (e == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
Collection参数构造分三种类型处理
- 1.SortedSet
SortedSet是一个接口，实现类是TreeSet,在这里可以认为是有序的Set,在initElementsFromCollection方法中将原SortedSet中的元素按照原来的顺序赋值给了自身的queue - 2.PriorityQueue
如果是PriorityQueue，将按原来的元素顺序赋值给自身的queue - 3 其他
按照自然顺序赋值，调用heapify()将数据调整为二叉堆
二叉堆是一种特殊的堆，是一棵完全二叉树或者是近似完全二叉树，同时二叉堆还满足堆的特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
二叉堆图解
Comparator参数构造
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
默认数组长度，将comparator比较器赋值
add(E e)和offer(E e)
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;
}
private void grow(int minCapacity) {
int oldCapacity = queue.length;
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
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;
}
add()调用offer(),两个方法走相同逻辑
- 1.判断插入元素是否为空，不允许插入
null - 2.修改次数++
- 3.元素个数大于等于
queue的容量就扩容，扩容规则:
原容量长度小于64，则增加原容量长度+2的长度，即扩容后的长度等于原长度的2倍+2；原容量长度大于等于64，则新增原容量长度的>>1,即新增原容量长度的一半
- 4.size+1,这里是size并非数组的长度，而是元素个数
- 5.如果是第1个添加的元素，就将第0个索引赋值，如果不是第一个添加的元素，将元素加入二叉堆“上移”。
上移siftUp(int k, E x) 方法在这里着重分析下，如果比较器comparator != null，则走siftUpUsingComparator(k, x)方法，否则走siftUpComparable(k, x)，siftUpComparable(k, x)方法则需要元素实现Comparable接口进行比较。siftUpUsingComparator(k, x)和siftUpComparable(k, x)上移逻辑是一样的。
siftUpComparable(k, x)方法分析
- k>0表示判断k不是根的情况下，也就是元素x有父节点
- 如果不是根节点，通过(k - 1) >>> 1拿到父节点，二叉堆获取父节点位置公式(n-1)/2
- 如果新增的元素k比其父节点e大，则不需要"上移"，跳出循环结束，否则与父节点交换位置，并将k指向父节点位置，进入下一层循环
- 找到新增元素x的合适位置k之后进行赋值
poll()
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;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
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;
}
poll()出队对于被删除元素来说，是下移。poll()主要逻辑
- 1.队列为空，返回
null - 2.元素个数-1
- 3.修改次数++
- 4.取出队首元素
result,队尾元素x - 5.当队尾索引不等于0，也就是队列中多于1个元素，下移，siftDown(int k, E x)逻辑:
下移siftDown(int k, E x) 方法在这里着重分析下，如果比较器comparator != null，则走siftDownUsingComparator(k, x)方法，否则走siftDownComparable(k, x)，siftDownComparable(k, x)方法则需要元素实现Comparable接口进行比较。siftDownUsingComparator(k, x)和siftDownComparable(k, x)下移逻辑是一样的。
siftDownUsingComparator(int k, E x)分析
参数说明:k表示移除元素下标0，x表示队尾元素
- int half = size >>> 1，无符号右移1位，等同于int half = size / 2 , 得到叶子节点索引half。
- 循环k < half,表示，下移最多下移到叶子节点。
- int child = (k << 1) + 1,获取左子节点索引，等同于int child = k * 2 + 1，右子节点索引等于左子节点索引+1
- Object c = queue[child]，c暂时表示左子节点的元素
- 当存在右子节点，并且通过比较器比较，c赋值为右子节点元素
- 如果队尾元素x比k索引的元素左右子节点都要小，则不需"下移"，结束循环
- 将queue索引k赋值为子节点的元素
- k = child,将k赋值为子节点索引，进入下一层循环
- 结束循环后将x 插入合适的位置
总结
- 1.PriorityQueue基于二叉堆实现
- 2.非线程安全
- 3.元素不能为null
- 4.PriorityQueue不是完全有序的，堆顶存储着最高优先级的元素
- 5.插入和移除元素时，按照优先级调整根节点元素
