PriorityQueue是优先队列，可以按照指定的优先级进行排序，比如某个元素优先级最高，当它插入队列时会被插到队列头。jdk优先队列是通过二叉堆实现的，类似堆排序，根节点始终是优先级最高的元素（其中优先级需要自定义，PriorityQueue的实现是小顶堆，也就是经过compareTo方法比较较小的元素的在顶部，所以我们可以定义数越小优先级越高），父结点的优先级要高于左右孩子结点，优先队列的调整时间复杂度是O(logn)。包括从上往下调整和从下往上调整，以满足二叉堆的性质。
PriorityQueue的类关系图如下：
package java.util;
import java.util.function.Consumer;
/**
* 优先队列，在队列里的顺序会按照指定的Comparator对象进行比较，
* 元素按照优先级高低进行排列，实现方式是平衡二叉堆,平衡二叉堆分为
* 大顶堆和小顶堆，此类实现是使用的小顶堆，可以重写元素的compareTo
* 方法或者重写Comparator接口的compare方法实现大顶堆
*/
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
*使用Object[]数组存放队列，将数组看做一个完全二叉树结构,则queue[n]的左孩子和
*右孩子分别为queue[2*n 1]和queue[2*(n 1)],并且需要满足父节点比孩子节点的优先级高
*
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 队列大小
*/
private int size = 0;
/**
* 元素比较对象，如果为空则使用元素自然排序,其中comparator限定了E或者
* E的父类实现了Comparator接口
*/
private final Comparator<? super E> comparator;
/**
* 优先队列修改次数
*/
transient int modCount = 0; // non-private to simplify nested class access
/**
* 初始化一个默认大小的队列，排序使用元素自然排序
*/
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) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* 初始化一个集合对象做为优先队列，传入的collection参数类型是E或者E的子类
*/
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
//如果c是SortedSet对象，则将SortedSet对象的排序方式赋值给优先队列的排序方式
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
//将SortedSet的比较器赋值给PriorityQueue的比较器
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
//如果c是优先队列，同上
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);
}
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified priority queue. This priority queue will be
* ordered according to the same ordering as the given priority
* queue.
*
* @param c the priority queue whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of {@code c} cannot be
* compared to one another according to {@code c}'s
* ordering
* @throws NullPointerException if the specified priority queue or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified sorted set. This priority queue will be ordered
* according to the same ordering as the given sorted set.
*
* @param c the sorted set whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of the specified sorted
* set cannot be compared to one another according to the
* sorted set's ordering
* @throws NullPointerException if the specified sorted set or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
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 initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray(); //将c转化为Object[]数组
// 如果c不是Object[]数组则转化为Object
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i )
if (a[i] == null)
throw new NullPointerException();
this.queue = a; //将数组赋值给队列
this.size = a.length; //修改大小
}
/**
* 将集合对象初始化为优先队列
*/
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
/**
* 数组最大值，Integer最大值减8,int最大值是2^31 - 1
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 增加数组容量
*/
private void grow(int minCapacity) {
//获取队列的容量
int oldCapacity = queue.length;
// 如果队列容量小于64，则新容量为2倍的旧容量 2，如果大于64则新容量为
//旧容量的3倍
int newCapacity = oldCapacity ((oldCapacity < 64) ?
(oldCapacity 2) :
(oldCapacity >> 1));
// 如果超过了数组最大限制，则调用hugeCapacity获取最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//获取一个新容量的数组对象
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果超过数组最大限制则返回Integer的最大值，否则返回数组最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 向优先队列添加一个元素
*/
public boolean add(E e) {
return offer(e);
}
/**
* 向优先队列添加一个元素
*/
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount ; //修改次数 1
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;
}
/**
* 获取队头元素
*/
@SuppressWarnings("unchecked")
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
//获取o第一次出现在队列中的位置
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i )
if (o.equals(queue[i]))
return i;
}
return -1;
}
/**
*移除指定元素
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
/**
* 移除第一次在队列中出现的元素
*/
boolean removeEq(Object o) {
for (int i = 0; i < size; i ) {
if (o == queue[i]) {
removeAt(i);
return true;
}
}
return false;
}
/**
*判断队列是否包含元素o
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 将队列复制为一个Object数组
*/
public Object[] toArray() {
return Arrays.copyOf(queue, size);
}
/**
* 将队列复制为一个指定类型的数组
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
final int size = this.size;
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(queue, size, a.getClass());
System.arraycopy(queue, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
/**
* 获取一个队列迭代器
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* 迭代器实现，由于是优先队列，要保持二叉堆的性质，所以在迭代过程
*中如果删除某元素可能会导致已经遍历的过得元素，移动到了被删除位置，末尾元素
* 被移动到了已经遍历过的位置。所以需要额外存储这些未遍历到但是移动到已经遍历
* 过的位置的元素。
*/
private final class Itr implements Iterator<E> {
/**
* 队列当前游标
*/
private int cursor = 0;
/**
* 上一次遍历到队列的位置
*/
private int lastRet = -1;
/**
* 在用iterator迭代过程中，如果有删除操作，会将末尾元素放到被删除位置进行调整，维持二叉堆的性质
* 如果元素被调整到被删除位置的上方，则将此元素加入双端队列，因为末尾的元素被删除，并且调整到的位置
* 已经遍历过了，所以为了防止遍历不到此元素，就会加入双端队列，对数组遍历完之后，就会对双端队列进行
* 遍历
*/
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;
//如果没被调整到lastRet的上方，则游标需要重新置为上次遍历的位置
if (moved == null)
cursor--;
else { //如果moved不为空说明调整到了lastRet的上方，则需要将moved加入到双端队列
if (forgetMeNot == null)
forgetMeNot = new ArrayDeque<>();
forgetMeNot.add(moved);
}
} else if (lastRetElt != null) { //如果移除的是双端队列的元素，则调用removEq
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw new IllegalStateException();
}
expectedModCount = modCount; //重新给期望修改值赋值
}
}
//获取队列大小
public int size() {
return size;
}
/**
*清空队列，对数组的每个元素都置为null
*/
public void clear() {
modCount ;
for (int i = 0; i < size; i )
queue[i] = null;
size = 0;
}
/**
* 获取队头元素，并且移除队头元素
*/
@SuppressWarnings("unchecked")
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;
//如果队列不为空，则向下调整二叉堆，这个不需要向上调整，因为位置0是根节点
if (s != 0)
siftDown(0, x);
return result;
}
/**
* 移除位置i的元素，在调整堆的时候如果最后一个元素被调整到位置i的上方
* 则返回最后一个元素，否则返回null
*/
@SuppressWarnings("unchecked")
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount ; //修改次数加一
int s = --size; //最后一个元素的位置，并且队列容量减一
if (s == i) //如果要移除的元素是最后一个元素则直接最后一个元素置空
queue[i] = null;
else {
E moved = (E) queue[s];//获取最后一个元素
queue[s] = null; //最后一个元素的位置置空
siftDown(i, moved); //将最后一个元素插入位置i并对堆做向下调整
//向下调整完，如果位置i的元素和最后一个元素相等，说明向下调整时
//各个元素的位置都没发生改变，说明i的孩子结点都符合堆的性质，然后
//需要向上做调整，看i的父节点是否满足堆的性质
if (queue[i] == moved) {
//向上调整
siftUp(i, moved);
//说明moved被调整到了i的上方，则返回moved，Iterator迭代器会使用这个结果
if (queue[i] != moved)
return moved;
}
}
return null;
}
/**
* 从下往上调整
*/
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上升到父结点
k = parent;
}
queue[k] = key;
}
/**
* 新插入的元素从下往上调整，满足二叉堆的性质
*/
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
/**
* 新插入的元素从上往下调整，满足二叉堆的性质
*/
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;
//half为第一个叶子节点
int half = size >>> 1;
while (k < half) {
int child = (k << 1) 1; // 左孩子位置
Object c = queue[child]; //左孩子值
int right = child 1; //右孩子位置
//找到左孩子和右孩子中的较小的
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
//如果key小于最小的，则直接退出循环，说明此结点满足二叉堆规则
if (key.compareTo((E) c) <= 0)
break;
//将最小的赋值给位置k
queue[k] = c;
k = child; //将最小位置的位置赋值给k，进行下次循环
}
queue[k] = key;//将x赋值给最后迭代到的k位置queue[k]
}
//
@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]; //找出最小的结点，并且将最小位置赋值给child
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;//将最小值赋值给queue[k]
k = child; //将最小值位置赋值给k，做下次迭代
}
queue[k] = x; //将x赋值给最后迭代到的k位置queue[k]
}
/**
* 将queue数组初始化为二叉堆.
*/
@SuppressWarnings("unchecked")
private void heapify() {
//从尾结点的父节点开始调整
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
/**
* 返回比较器对象
*/
public Comparator<? super E> comparator() {
return comparator;
}
}
