简介
PriorityQueue 从字面意思可以知道这是一个优先级队列类。其底层是用数组存储元素，通过二叉堆数据结构对元素排序，默认是最小堆，在创建 PriorityQueue 对象的时候可以指定排在堆头的元素是最小或者最大。
使用场景
- 数据的筛选：在数据量很大的情况下，找到最小的3个数据
- 功能复用：在 DelayQueue 类中，采用组合的手段复用 PriorityQueue 类，可以根据过期时间做优先级排序，越快过期的元素过靠近队列头部
除此之外，有一个和 PriorityQueue 类的实现类似的阻塞队列——PriorityBlockingQueue，所以学好 PriorityQueue 不仅有助于学好 DelayQueue 的源码，还有助于学好 PriorityBlockingQueue 源码！
接下来通过一个Demo学习如何使用 PriorityQueue 类吧！
public class PriorityQueueDemo {
public static void main(String[] args) {
// 第一种：使用 PriorityQueue 默认的比较器，对象排序是升序
// PriorityQueue<Integer> priorityQueue = new PriorityQueue();
// 第二种：自定义比较器
// PriorityQueue<Integer> priorityQueue = new PriorityQueue(new Comparator<Integer>() {
// @Override
// public int compare(Integer o1, Integer o2) {
// // 降序
// return o2-o1;
// }
// });
// 第三种：其实和第二种方式一样，只不过使用Lambda表达式更加优雅
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>((x,y)-> x.compareTo(y));
priorityQueue.add(6);
priorityQueue.add(10);
priorityQueue.add(2);
priorityQueue.add(8);
while(!priorityQueue.isEmpty()){
System.out.println(priorityQueue.poll());
}
}
}
输出：
10
8
6
2
示例中提供了 PriorityQueue 类两种创建对象的方式。实际上，PriorityQueue 的构造函数还提供了多种创建对象的方式，稍后看 PriorityQueue 的源码将会更加清楚。
源码剖析
学习一个类的源码，应该先从类注释开始阅读，这有利于让我们快速了解这个类的基本信息
查看类注释可以大概的得出以下信息：
- 基于堆结构的无界优先级队列
- 不允许有空对象
- 对象如果没有实现 Comparable 接口，则必须实现 Comparator 接口，否则会抛异常
- 线程不安全
成员变量
// 默认初始化大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 用数组实现的二叉堆
// 父节点的位置是n，那么左孩子的位置是2*n+1，右孩子的位置是2*（n+1）
transient Object[] queue;
// 队列的元素数量
private int size = 0;
// 比较器
private final Comparator<? super E> comparator;
// 修改版本
transient int modCount = 0;
// 数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造方法：
// 默认的构造方法。入队的元素必须实现Comparable接口
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 指定初始大小，入队元素必须实现Comparable接口
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) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
// 初始化数组
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// 根据Collection集合初始化优先队列
public PriorityQueue(Collection<? extends E> c) {
// 如果集合是SortedSet类型
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类型
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
} else {// 如果集合是Collection类型
this.comparator = null;
initFromCollection(c);
}
}
// 参数指定PriorityQueue对象初始化优先队列
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
// 参数指定SortedSet初始化优先队列
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
初始化优先队列的相关方法
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
// 判断参数对象是否是PriorityQueue类型，如果是则将优先队列c中的数组和数组大小赋值给当前优先队列对象中
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
// 从集合中初始化数据到队列，集合中不允许有null元素
private void initElementsFromCollection(Collection<? extends E> c) {
// 将参数对象转为数组
Object[] a = c.toArray();
// 如果c.toArray()不能转化为Object数组，则通过调用Arrays类的copyOf方法，将其转换为Object类型的数组
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
// 数组长度
int len = a.length;
if (len == 1 || this.comparator != null)
// 如果数组内有null元素，则抛出异常
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
// 将数组a的值赋值给当前优先队列的queue
this.queue = a;
// 将数组的长度赋值给当前优先队列的size
this.size = a.length;
}
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
// 调用heapify方法重新将数据调整为一个二叉堆
heapify();
}
// 将数据调整为一个二叉堆
@SuppressWarnings("unchecked")
private void heapify() {
//因为调用的是下移的操作，所以需要去掉所有的叶子节点
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);// 稍后再解释 siftDown 方法的源码
}
当构造方法中传入 PriorityQueue 类型的对象，就会直接赋值给当前的优先队列对象，否则就会经过上述的某些initXXX方法，将集合转换为数组后调用heapify方法，把数组内的元素排序。
添加数组元素
// 添加数组元素
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
// 添加的元素不能为null
if (e == null)
throw new NullPointerException();
// 改变队列结构，modCount自增记录改变次数
modCount++;
int i = size;
// 如果size大于等于了数组的长度，则进行扩容操作（grow的源码，稍后再展示出来）
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
//如果size=0的话直接放入顶
queue[0] = e;
else
// 根据元素的大小插入合适的位置，保证堆结构中元素的排序
siftUp(i, e);
return true;
}
// 在k位置插入元素x
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;
}
// 与 siftUpComparable 方法相似
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;
}
以上就是往 PriorityQueue 对象添加元素的核心源码。为了加深理解，我根据文章开头的示例，画了张流程图。建议不理解的朋友，多debug，相信会豁然开朗的！
1.找出插入位置的父节点（对应源码的 k >>> 1）
2.比较新增节点和父节点大小，如果父节点值小于新增节点值，代表新增节点属于父节点的子节点；否则继续继续往堆顶走，直到找出比新增节点更小的节点成为其子节点或成为堆头
读取数组元素
// 读取栈头元素
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
//将队列根元素取出，并重新调整堆排序
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;
}
// 在k位置插入元素x
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
// 向队列中位置为k的地方插入元素x
private void siftDownComparable(int k, E x) {
// 添加的元素需要实现Comparable接口，用于比较大小
Comparable<? super E> key = (Comparable<? super E>) x;
// 保证循环到最下面的非叶子节点
int half = size >>> 1;
// 当k<half说明k节点有子节点。因为二叉堆中，叶子节点占一半的元素
while (k < half) {
// 取k节点的左子节点位置
int child = (k << 1) + 1; // assume left child is least
// 取k节点的左子节点元素c
Object c = queue[child];
//取k节点的右子节点位置
int right = child + 1;
// right < size说明k节点是有两个节点，则比较左右节点的大小
// 当左节点大于右节点时，将右节点的值赋给左节点c，即找出k的最小子节点
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;
}
// 与 siftDownComparable 方法流程相似
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 remove(Object o) {
// 根据元素查找数组对应的下标
int i = indexOf(o);
// 如果下标为-1，则代表数组没有指定的元素
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;
}
// 移除指定位置的元素
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
// 如果要删除的节点在队列尾部，直接将队列尾部的元素设置为null
if (s == i)
queue[i] = null;
else {
// 取出最后一个元素，然后将其位置的元素设置为null
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
删除元素的逻辑和流程图可以参考上面siftDown的流程，基本一样。
扩容
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 如果长度小于64，则添加到原来的2倍，如果大于64，则增加为原来的一半
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// 如果新数组容量大于整型的最大值-8则执行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();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
扩容很简单，首先需要计算出扩容后数组的长度，然后通过Arrays.copyOf方法将原数组的值搬到新数组。
其它常用方法：
// 迭代数组，查找数组中对应元素的下标，没有的话返回-1
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 int size() {
return size;
}
//清空队列，通过for循环遍历将所有元素置为null
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}
// 是否包含节点
public boolean contains(Object o) {
return indexOf(o) != -1;
}
// 将队列转为Object数组返回
public Object[] toArray() {
return Arrays.copyOf(queue, size);
}
// 将队列转为指定类型的数组返回
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;
}
总结
根据以上的源码剖析，可以得出以下几点：
- PriorityQueue 对象不是线程安全（并没有使用任何线程安全相关的方法）
- 二叉堆并不是有序的，只是保证堆头元素是堆内最小值，每次取的时候只取堆头元素，如果没看过源码的话很容易误以为是有序的
- 队列内的元素不能是null，而且元素必须实现Comparable接口或Comparator接口
如果觉得源码剖析不错的话，麻烦点个赞哈！对于文章有哪里不清楚或者有误的地方，欢迎在评论区留言~
网友评论