概述
PriorityQueue这个队列不知道大家使用过吗，反正我从来没有用过，主要对它不是很了解，今天我带领大家剖析下PriorityQueue这个优先级队列。
PriorityQueue介绍
顾名思义，PriorityQueue是优先队列的意思。优先队列的作用是能保证每次取出的元素都是队列中权值最小的。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器。
- PriorityQueue实现了Queue接口，最大的特点是存取具有优先级，就是根据元素的顺序来决定
- PriorityQueue是一个无界的容器
- PriorityQueue底层是基于堆实现的
- 不允许放入null元素
- PriorityQueue不是线程安全的
以上是PriorityQueue的类图,
- 继承了AbstractQueue抽象类，实现了Queue接口，具备队列的操作方法
- 实现了Seriablizable接口，支持序列化
构造方法
| 方法 | 说明 |
| PriorityQueue() | 构造一个初始容量为11的优先队列 |
| PriorityQueue(Comparator<? super E> comparator) | 构造一个自定义排序器的优先队列 |
| PriorityQueue(SortedSet<? extends E> c) | 构造一个基于SortedSet内容的优先队列 |
关键方法
| 方法 | 说明 |
| add(E e) | 添加元素，如果超过队列长度，抛出异常 |
| offer(E e) | 添加元素，如果超过队列长度返回false |
| remove() | 获取下个元素，如果没有抛出异常 |
| poll() | 获取下个元素，如果没有返回null |
| element() | 查看下个元素的内容，如果没有抛异常 |
| peek() | 查看下个元素的内容，如果没有返回null |
使用案例
- 优先队列功能测试
@Test public void test1() { Queue<Integer> queue = new PriorityQueue<>(); queue.offer(5); queue.offer(4); queue.offer(1); queue.offer(9); queue.offer(3); queue.offer(2); // 打印，排序 Integer poll = null; while ((poll = queue.poll()) != null) { System.out.println(poll); } }
运行结果：
- 自定义排序器
@Test public void test2() { // 自定义排序，倒序 Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder()); queue.offer(5); queue.offer(4); queue.offer(1); queue.offer(9); queue.offer(3); queue.offer(2); // 打印，排序 Integer poll = null; while ((poll = queue.poll()) != null) { System.out.println(poll); } }
运行结果：
核心机制
实现机制
PriorityQueue通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。
上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
源码解析
成员变量
transient Object[] queue; /** * The number of elements in the priority queue. */ private int size = 0; /** * The comparator, or null if priority queue uses elements' * natural ordering. */ private final Comparator<? super E> comparator; /** * The number of times this priority queue has been * <i>structurally modified</i>. See AbstractList for gory details. */ transient int modCount = 0;
- queue就是实际存储元素的数组。
- size表示当前元素个数。
- comparator为比较器，可以为null。
- modCount记录修改次数。
构造方法
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; }
- 初始化了queue和comparator
添加元素offer
public boolean offer(E e) { // 如果元素为空，抛出空指针 if (e == null) throw new NullPointerException(); // 修改次数+1 modCount++; int i = size; // 首先确保数组长度是够的，如果不够，调用grow方法动态扩展。 if (i >= queue.length) grow(i + 1); size = i + 1; // 如果是第一次添加，直接添加到第一个位置即可 (queue[0]=e) if (i == 0) queue[0] = e; else // 否则将其放入最后一个位置，但同时向上调整，直至满足堆的性质 (siftUp) siftUp(i, e); return true; }
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); }
如果原长度比较小，大概就是扩展为两倍，否则就是增加50%，使用Arrays.copyOf方法拷贝数组。
private void siftUp(int k, E x) { // 如果比较器为空 if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }
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; }
参数k表示插入位置，x表示新元素。k初始等于数组大小，即在最后一个位置插入。代码的主要部分是：往上寻找x真正应该插入的位置，这个位置用k表示。
怎么找呢？新元素(x)不断与父节点(e)比较，如果新元素(x)大于等于父节点(e)，则已满足堆的性质，退出循环，k就是新元素最终的位置，否则，将父节点往下移(queue[k]=e)，继续向上寻找。
总结
优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个，其他没有特定顺序。查看头部元素的效率很高，为O(1)，入队、出队效率比较高，为O(log2(N))，构建堆的效率为O(N)。根据值查找和删除元素的效率比较低，为O(N)。
