PriorityQueue 优先级队列
前世今生
extends AbstractQueue
AbstractQueue extends AbstractCollection implements Queue
实现原理大白话
内部使用你所熟悉的数据结构最堆来实现，每次都是取堆顶的元素。至于堆怎么实现，其实很简单，就一个数组而已，这里就不讨论怎么实现堆了。默认是根据传入的对象进行比较建立初始堆的。比如说 String 实现了 Comparable 接口，里面就是根据这个进行排序建立初始堆的。
主要的构造函数
// 可以使用外排序 Comparator 来构建你自己的堆，默认为空
// initialCapacity 为初始堆大小，一般来说，为了避免扩容，或者空间浪费，我们要选择合适的值，默认值为 DEFAULT_INITIAL_CAPACITY = 11
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
常用的方法
添加元素
public boolean add(E e) {
return offer(e);
}
// 调用的是offer
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
// 几乎所有的集合类都有这个，顾名思义，主要是记录修改次数，实际上是为了防止你在遍历的时候更改了数据，造成不一致，会抛出ConcurrentModificationException 异常，注意，这与并发没有多大联系
modCount++;
int i = size;
// 检查是否需要扩容，queue就是真实数据
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
// 使用经典的 siftUp 上移最后添加的元素， 保证我们的堆还是有序的
siftUp(i, e);
return true;
}
删除元素
// 同样使用 siftDown，首先将最后一个元素移到堆顶，再调整堆即可
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;
}
获取堆顶元素
// 直接数组返回
// 也可以使用 element()，是 abstractQueue 的方法，调用的也是 peek() 再一次感受到多态对象的强大
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
获取后一位置的元素
// 因为使用的是最堆的数据结构，所以只能遍历，效率较低
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
关于siftUp
// 如果没有外排序，则使用内排序
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(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;
}
