PriorityQueue实际上是一个小根堆（大根堆），具体堆顶元素是最大元素还是最小元素取决于你传入的比较器，默认是小根堆，即每次堆顶拿到的是最小的元素。
我们来看一下实例
public static void main(String[] args) {
PriorityQueue q = new PriorityQueue<>((a,b)->a[0]-b[0]);
q.add(new int[]{2,5});
q.add(new int[]{1,6});
q.add(new int[]{3,2});
q.add(new int[]{4,9});
q.add(new int[]{5,1});
System.out.println("hello");
}
运行上述代码，可以得到一个小根堆，并且是根据int数组的第一个元素进行比较的。
如上图所示，左边是在内存中的实际存储顺序，右边则是逻辑上的存储顺序。
那么如果我们改变一下改变的元素，使用数组中第二个元素进行比较会发生什么呢
public static void main(String[] args) {
PriorityQueue q = new PriorityQueue<>((a,b)->a[1]-b[1]);
q.add(new int[]{2,5});
q.add(new int[]{1,6});
q.add(new int[]{3,2});
q.add(new int[]{4,9});
q.add(new int[]{5,1});
System.out.println("hello");
}
运行上述代码，可以得到如下结果
可以发现，在实际存储时，第二个元素并不是严格有序的，在逻辑上则表示为某个结点的值比其孩子结点要小，这样就能保证每次取最顶上的元素都是最小的。
接下来我们来探讨一下比较常用方法的源码。
首先是属性public class PriorityQueueextends AbstractQueue implements java.io.Serializable { private static final long serialVersionUID = -7720805057305804111L; private static final int DEFAULT_INITIAL_CAPACITY = 11; transient Object[] queue; // non-private to simplify nested class access private int size = 0; private final Comparator comparator; transient int modCount = 0; // non-private to simplify nested class access ... }
可以看到，PriorityQueue的内部存储结构是Object数组，并且在没有指定数组容量的时候，默认容量是11。
构造函数PriorityQueue的构造函数有很多，我们就看文章开头例子用到的那个，那个也是最常用的。
public PriorityQueue(Comparator comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
可以发现，我们需要传入一个比较器作为参数。还记得开头我们的初始化方法吗，我们使用了lambda表达式，并且这种写法等价于下的写法
public static void main(String[] args) {
//PriorityQueue q = new PriorityQueue<>((a,b)->a[1]-b[1]);
PriorityQueue q = new PriorityQueue<>(new Comparator() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
q.add(new int[]{2,5});
q.add(new int[]{1,6});
q.add(new int[]{3,2});
q.add(new int[]{4,9});
q.add(new int[]{5,1});
System.out.println("hello");
}
也就是说，继承Comparator
既然是使用数组作为基本的存储结构，那么就需要有扩容的方法
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
我们就看最核心的扩容方案
int newCapacity = oldCapacity+((oldCapacity<64)?(oldCapacity+2):(oldCapacity>>1));
如果原来的容量小于64，那么新容量就是2*oldCapacity+2；
如果原来的容量大于等于64，那么新容量就是1.5*oldCapacity
常用方法
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;
}
add(E e)和offer(E e)方法用于添加元素，其基本逻辑是首先判断容量是否足够，如果不足够就添加容量，然后将元素插入到最后的位置，再调整整个堆。
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 key = (Comparable) 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;
}
@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;
}
siftUp(int k, E x)方法中有一个判断，如果我们指定了比较器，就用我们所指定的比较器，否则就是用元素的自然顺序（按照元素的本身的比较规则去比较）。
其中使用比较器的方法是siftUpUsingComparator(int k, E x)，我们重点看这个方法。
这个方法的逻辑是，对于位置为k的结点，比较其和父结点的大小，如果比其父结点小，那么就将父结点交换到其原来位置。不断重复这个过程，直到其父结点比其要小或者已经到达了根结点为止。此时，k所指向的位置就是元素x应该待的位置。
@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;
if (s != 0)
siftDown(0, x);
return result;
}
poll()方法用于弹出根结点，并且将最后一个元素放到根结点的位置开始向下调整。poll()调用了siftDown(int k, E x)方法来向下调整，接下来我们来看一下siftDown(int k, E 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 key = (Comparable)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable) 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;
}
@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];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
siftDown(int k, E x)方法的逻辑与siftUp(int k, E x)方法是非常类似的。
我们重点看一下siftDownUsingComparator(int k, E x)这个方法
首先half指向的是第一个叶子结点，我们需要调整所有非叶子结点。
对于每一个待调整的结点，首先找出他的左右孩子中较小的那个，如果这个较小的孩子结点比x小，那么就将较小的孩子结点移动到k处，令k指向较小孩子结点。
重复上述循环，直到x比位置k的孩子结点都要小或者k大于等于half了，那么就结束循环，此时k所指向的位置就是该元素应该待的位置。
上述逻辑实际上就是堆排序的过程，如果觉得我说的不清楚可以看看下面教程
图解排序算法(三)之堆排序 - dreamcatcher-cx - 博客园
总结PriorityQueue在算法题中还是挺常用的，今天就遇到了一道使用先序队列的贪心算法题
https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/
希望这篇文章能对你有帮助O(∩_∩)O哈哈~
