PriorityBlockingQueue（优先阻塞队列）是Java并发包java.util.concurrent下面的一个工具类，它除了具有阻塞队列的功能外还具有以下特点：

对队列中的元素进行排序，如果未指定比较器，插入队列的元素必须实现Comparable接口内部基于数组实现的最小二叉堆算法队列的长度是可扩展的（类似ArrayList），上限为Integer.MAX_VALUE - 8PriorityBlockingQueue例子

假设在医院挂号的场景，大家都在依次排队，这时候来了一位80岁以上老年人，我们应该优先让老年人挂号，代码可以这样实现：

public static void main(String[] args) {        PriorityBlockingQueue<Patient> pbq = new PriorityBlockingQueue<>(10);        for (int i = 0; i < 3; i++) {            Patient patent = new Patient("Patent" + i, 20 + i);            pbq.offer(patent);        }        Patient oldMan = new Patient("OldMan", 88);        pbq.offer(oldMan);                Patient patient = null;        do {            patient = pbq.poll();            if (patient != null) {                System.out.println(patient.name + "挂号成功！");            }        } while (patient != null);    }        static class Patient implements Comparable<Patient> {        private String name;        private Integer age;        private long waitingTime;                public Patient(String name, Integer age) {            this.name = name;            this.age = age;            this.waitingTime = System.nanoTime();        }                @Override        public int compareTo(Patient o) {            if (age >= 80) {                return -1;            } else if (o.age >= 80) {                return 1;            }            return waitingTime < o.waitingTime ? -1 : 1;        }}

例子中三个二十几岁的年轻人先排着队，他们的优先级以他们的排队时间waittingTime为准，年龄超过80岁的老年人则具有优先权，当姓名为OldMan的老年人加入队列后，具有最高优先权，下面的打印日志也证明了这一点：

OldMan挂号成功！Patent0挂号成功！Patent1挂号成功！Patent2挂号成功！

那么PriorityBlockingQueue是如何实现上述例子中的功能呢？下面我们通过它的两个典型方法offer和poll来分析下它的底层逻辑和原理。

offer内部主要调用了三个方法：

tryGrow：内部数组长度不够进行数组扩展。PriorityBlockingQueue内部元素是存储在一个内部数组上的，当数组长度不够时需要进行相应的扩展（大体上是扩展原来的0.5倍，和ArrayList类似）。siftUpComparable：对新增的元素进行最小二叉推排序，未指定比较器时调用该方法使用元素自身实现的Comparator.compareTo()方法进行比较排序。siftUpUsingComparator：对新增的元素进行最小二叉推排序，指定了比较器时调用该方法使用指定的比较器进行比较排序。

public boolean offer(E e) {        if (e == null)            throw new NullPointerException();        final ReentrantLock lock = this.lock;        lock.lock();        int n, cap;        Object[] array;        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.signal();        } finally {            lock.unlock();        }        return true;}

最小二叉堆算法保证的是内部数组queue[i]的值比queue[2*i]和queue[2*i+1]要小，这样就能保证queue[0]一直是最小的，当执行poll操作取值时，只要拿queue[0]就可以了。

关于最小二叉堆算法，它的时间复杂度为 ，相关算法也比较简单，平台内或者其他搜索引擎都可以搜到，这里不多做解释。

上述例子中，当三个年轻人加入队列后，以及80岁老人OldMan加入队列后，内部数组的分配如下图所示：

前三个人是依次排队，当OldMan加入后首先加入到数组尾部queue[3]的位置，然后和queue[3]的父节点queue[1]进行比较，OldMan优先queue[1]和queue[3]互换，然后queue[1]和它的父节点queue[0]进行比较，OldMan优先queue[0]和queue[1]互换。

poll内部主要调用了dequeue中的两个方法：

siftDownComparable：当从队列首部取出元素时，通过向下遍历的方式将合适的元素填充队列首部queue[0]，未指定比较器时调用，此时通过元素自身实现的Comparator.compareTo()方法进行比较排序。siftDownUsingComparator：当从队列首部取出元素时，通过向下遍历的方式将合适的元素填充队列首部queue[0]，指定比较器时调用，此时通过比较器进行比较排序。

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;        }}

上述例子中当poll第一个元素（即OldMan）时，PriorityBlockingQueue内部数组的变化过程如下：

其过程是将队列首部即queue[0]的两个子节点Patient0和Patient2进行比较，取其中小的和队列尾部节点Patient1比较，发现Patient0最小，然后将Patient0放到队列首部，并将Patient1放入原Patient0的位置queue[1]（如果此时队列中不止三个元素，还要将queue[1]的两个子节点的最小者和Patient1进行比较，如此递归下去）。

Demo代码位置

src/main/java/net/weichitech/juc/PriorityBlockingQueueTest.java · 小西学编程/java-learning - Gitee.com

相关文章

JAVA并发之BlockingQueue（阻塞队列）

JAVA并发之ReentrantLock原理解析