PriorityBlockingQueue 支持优先级排序的无界阻塞队列, 默认情况下元素采取自然顺序升序排列。也可以自定义类实现 compareTo()方法来指定元素排序规则，或者初始化 PriorityBlockingQueue 时，指定构造参数 Comparator 来对元素进行排序。
构造函数
public PriorityBlockingQueue() { // 设置的默认长度，为11 this(DEFAULT_INITIAL_CAPACITY, null); } // 设置长度的构造函数 public PriorityBlockingQueue(int initialCapacity) { this(initialCapacity, null); } // 真正创建队列的构造函数 public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) { if (initialCapacity < 1) throw new IllegalArgumentException(); this.lock = new ReentrantLock(); this.notEmpty = lock.newCondition(); this.comparator = comparator; this.queue = new Object[initialCapacity]; } // 构造且赋值的构造方法，在构造队列的时候旧传递的默认值 public PriorityBlockingQueue(Collection<? extends E> c) { this.lock = new ReentrantLock(); this.notEmpty = lock.newCondition(); boolean heapify = true; // true if not known to be in heap order boolean screen = true; // true if must screen for nulls if (c instanceof SortedSet<?>) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c; this.comparator = (Comparator<? super E>) ss.comparator(); heapify = false; } else if (c instanceof PriorityBlockingQueue<?>) { PriorityBlockingQueue<? extends E> pq = (PriorityBlockingQueue<? extends E>) c; this.comparator = (Comparator<? super E>) pq.comparator(); screen = false; if (pq.getClass() == PriorityBlockingQueue.class) // exact match heapify = false; } Object[] a = c.toArray(); int n = a.length; // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, n, Object[].class); if (screen && (n == 1 || this.comparator != null)) { for (int i = 0; i < n; ++i) if (a[i] == null) throw new NullPointerException(); } this.queue = a; this.size = n; if (heapify) heapify(); }PriorityBlockingQueue维护的属性类似于ArrayBlockingQueue但是其提供了comparator属性来维护一个排序策略，这样来实现队列的排序。
关于PriorityBlockingQueue的数据添加类似其他的Queue提供了add、offer、put三个方法。
add和put
public boolean add(E e) { return offer(e); } public void put(E e) { offer(e); // never need to block }根据上面的代码我们可以明白两个内容：
PriorityBlockingQueue添加数据的方法其实至于offerPriorityBlockingQueue并没有提供阻塞方法来添加数据offer
public boolean offer(E e) { if (e == null) throw new NullPointerException(); final ReentrantLock lock = this.lock; lock.lock(); int n, cap; Object[] array; // 如果此时size大于queue（数组长度），数据满 while ((n = size) >= (cap = (array = queue).length)) // 尝试扩容数组 tryGrow(array, cap); try { Comparator<? super E> cmp = comparator; // 使用排序逻辑 if (cmp == null) // 采用自然排序 siftUpComparable(n, e, array); else // 自定义排序策略 siftUpUsingComparator(n, e, array, cmp); size = n + 1; // 唤醒notEmpty阻塞的线程 notEmpty.signal(); } finally { lock.unlock(); } return true; }关于阻塞
和ArrayBlockingQueue不同之处，其并没有进行阻塞，因为ArrayBlockingQueue是一个固定长度的数组，而对于PriorityBlockingQueue其提供了扩容机制，这样就不存在等待空间的操作。
加锁逻辑
此时队列需要进行扩容，但是扩容是一个极其消耗资源的动作，此时假如还持有锁会导致其他线程无法进行出队操作。所以扩容前释放了锁，方便其他线程进行出队操作。此时我们只允许一个线程可以进行扩容。所以使用CAS的方式来保证只有一个线程进行操作。CAS失败的线程会调用Thread.yield()让出cpu资源，目的是为了让扩容线程扩容后优先调用 lock.lock 重新获取锁。当然这里不先释放锁也是可以的，也就是在整个扩容期间一直持有锁，那么其他线程在这个时候是不能进行出队和入队操作的。
扩容路基
扩容的主要逻辑在这里
int newCap = oldCap + ((oldCap < 64) ? (oldCap + 2) : // grow faster if small (oldCap >> 1));扩容的幅度取决于是否大于64。如果小于则扩大oldCap + 2，否则扩大一半。
可以看到其并不是简单的进行线性排序，其排序策略是类似小跟堆这种将最小值放入到最上方。
我们可以模拟这个插入过程：
此时我们插入2。因为while (k > 0) 条件没有进入直接在k位添加元素2
k=0 2 null null null null此时我们插入8。此时获取的int parent = (k - 1) >>> 1为0。其根节点为0.并且插入值大于根节点则直接在k为添加元素8
k=1 2 8 null null null此时我们插入6。此时获取的int parent = (k - 1) >>> 1为0。其根节点为0.并且插入值大于根节点则直接在k为添加元素6
k=2 2 8 6 null null此时我们插入10。此时获取的int parent = (k - 1) >>> 1为0。其根节点为1.并且插入值大于根节点则直接在k为添加元素10
k=3 2 8 6 10 null此时我们插入3。此时获取的int parent = (k - 1) >>> 1为0。其根节点为1.此时发现插入元素并不大于根节点，则将根节点插入到k位
k=4 2 8 6 10 8然后将k指向为1，然后此时k位的根节点为0，而插入元素3是大于2的，所以直接将元素3插入k为。最后队列为
k=1 2 3 6 10 8很显然上面的队列我们认为的有序是不一致的。但是我们把队列变形下看看
2 3 6 10 8这样就可以看到其是一个标准的小跟堆。
类似其他队列内容，依旧提供了peek、poll、take三个方法查询元素，始终poll和take在查询元素的时候会进行移除，而peek只是进行简单的查看。
public E peek() { final ReentrantLock lock = this.lock; lock.lock(); try { return (size == 0) ? null : (E) queue[0]; } finally { lock.unlock(); } }可以看到因为数据队列使用了小根堆得排序方式，所以0位置是其根节点，一定是最小的元素，所以只需要查询0位的元素
poll和take
public E poll() { final ReentrantLock lock = this.lock; lock.lock(); try { return dequeue(); } finally { lock.unlock(); } } public E take() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lockInterruptibly(); E result; try { while ( (result = dequeue()) == null) notEmpty.await(); } finally { lock.unlock(); } return result; }poll和take都是获取最新的元素且会进行元素移除的逻辑，区别在于take会进行阻塞获取。其中使用Condition(notEmpty)来进行阻塞的方法，这边不再讲了，之前最开始介绍queue的文章中有说明。
dequeue
和之前队列实现类一样其实现数据查询\删除最终是使用dequeue的方法。
private E dequeue() { int n = size - 1; if (n < 0) return null; else { Object[] array = queue; E result = (E) array[0]; E x = (E) array[n]; array[n] = null; Comparator<? super E> cmp = comparator; if (cmp == null) siftDownComparable(0, x, array, n); else siftDownUsingComparator(0, x, array, n, cmp); size = n; return result; } }关于移除的逻辑也很简单主要涉及：
返回首位元素的值修改size数据长度查询\移除元素逻辑的重点在于其siftDownComparable方法。在移除掉最小的数据之后，需要使用其重建小跟堆。
private static <T> void siftDownComparable(int k, T x, Object[] array, int n) { if (n > 0) { Comparable<? super T> key = (Comparable<? super T>)x; int half = n >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = array[child]; int right = child + 1; if (right < n && ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) c = array[child = right]; if (key.compareTo((T) c) <= 0) break; array[k] = c; k = child; } array[k] = key; } }整个逻辑用文字描述可以是下面内容：
首先我们拿到最后一个节点的非叶节点，得到了2。然后我们发现其并非根节点。int child = (k << 1) + 1;首先我们获得根节点的左节点。int right = child + 1;然后获得根节点的右节点假如此时右节点小于最后节点，并且左节点大于右节点，则设置子节点为右节点如果最后节点小于根节点最小子节点，则终端，设置0位置为最后节点，将根节点的最小节点数据设置到k为，然后设置k为位child位置我们使用之前的例子来模拟下这个流程：
这个一个最开始的队列，现在我们移除0位的元素。
x=8,n=4,k=0 2 3 6 10 null然后我们得到下面内容:
half = 2
第一轮循环中我们可以达到下内容
// 0 < 2 while (k < half) { // child = 1 int child = (k << 1) + 1; // assume left child is least // c = 3 Object c = array[child]; // right = 2 int right = child + 1; // 3 > 6 = false if (right < n && ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) c = array[child = right]; // 8 <= 3 = false if (key.compareTo((T) c) <= 0) break; // [0] = 3 array[k] = c; // k = 1 k = child; } x=8,n=4,k=1 3 3 6 10 null第二轮循环中我们可以达到下内容
while (k < half) { // child = 3 int child = (k << 1) + 1; // assume left child is least // c = 10 Object c = array[child]; // right = 4 int right = child + 1; // 4 < 4 false if (right < n && ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) c = array[child = right]; // 8 <= 10 = true if (key.compareTo((T) c) <= 0) break; // [0] = 3 array[k] = c; // k = 1 k = child; }此时循环终端，然后array[k] = key;将K位置设置为key的值。key为固定的8，而k在上一循环已经被设置为了1。
x=8,n=4,k=1 3 8 6 10 null转换成小根堆为
3 8 6 10 null个人水平有限，上面的内容可能存在没有描述清楚或者错误的地方，假如开发同学发现了，请及时告知，我会第一时间修改相关内容。假如我的这篇内容对你有任何帮助的话，麻烦给我点一个赞。你的点赞就是我前进的动力。
