Java1.8-PriorityQueue源码解析

概述

  首先，Priority翻译之后是优先级的意思，而PriorityQueue，也就是优先级队列的意思。优先级队列，和普通的先进先出（FIFO）的队列不同，优先队列每次取出的元素都是队列中优先级最高的，而PriorityQueue默认优先级是取出元素最小的值，当然也可以按照我们指定的规则来自定义优先级。
首先，我们先看下官方API：
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
通过文档，我们可以看到PriorityQueue优先级队列的一些性质：

1. PriorityQueue是基于优先级堆来实现的无界优先队列，是在JDK1.5之后引入的类；
2. 优先队列的元素按照它们的自然排序顺序排列，或者根据使用的构造方法提供的比较器来进行排序；
3. 优先队列不允许null元素；
4. 优先队列不允许插入非可比的对象，有可能会抛出ClassCastException，比如对int排序，你添加了一个字符串类型的元素。
5. 该优先队列每次取出的元素都是最小的。接口offer, poll, remove(),add方法，查询时间都是O(log(n))，
6. 优先队列迭代器迭代的顺序无法保证，如果想有序遍历，请考虑使用Arrays.sort(priorityQueue.toArray())；而对于remove(Object) and contains(Object)方法，查询是线性时间；而对于peek, element, and size方法，查询是常数时间。
7. 该优先队列不是线程安全的，如果要在线程安全的场景下使用，建议使用线程安全的PriorityBlockingQueue类（优先级阻塞队列）；

  PriorityQueue是基于堆来实现的，而堆这个数据结构是怎样的呢。我们来大概说下，学过数据结构的应该都知道，堆是利用完全二叉树来进行处理数据，而完全二叉树又是怎样的呢。

  若二叉树的深度是h，那么除第h层外，其他各层（1～h-1）层的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。而堆就是基于这种数据结构来处理数据的。我们用一张图大致来看下完全二叉树：

完全二叉树图示

  如图所示，图1是完全二叉树，而图二由于第三层所有的节点并非连续集中在最左侧，所以不是完全二叉树；而图三，由于第三层的结点没有达到最大个数（最大个数是4），所以也不是完全二叉树。

其中堆一般还分为两种：最大堆和最小堆。

1. 顾名思义，最小堆就是根结点是所有数据中最小的元素，并且堆中每个结点的值总是不大于其孩子结点的值。
2. 而最大堆就是根结点是所有结点中最大的元素，并且堆中每个结点的值总是不小于其孩子结点的值。

  而PriorityQueue则是基于最小堆来实现的，并且底层是通过数组来构建堆的数据结构。由于本文的重点并不是堆亦或是完全二叉树，所以堆的介绍就到这里来了。接下来我们来学习PriorityQueue的源码。

继承结构及属性

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    
    // 使用数组来构造堆，也就是优先级队列
    transient Object[] queue;
    // 数组默认的初始化容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    // 队列的容量
    private int size = 0;
    // 比较器
    private final Comparator<? super E> comparator;
    // 结构化修改次数
    transient int modCount = 0;
    // 数组最大容量限制，Integer最大值-8是说一些虚拟机可能会在数组中保留一些header words的空间，
    // 所以没有取Integer最大值
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

首先，PriorityQueue是继承自AbstractQueue，AbstractQueue则是实现了Queue接口，封装了一些队列基础的方法。

1. 优先队列底层使用数组来操作数据，并且数组的默认初始化容量是11，如果我们没有指定比较器，那系统将按照自然顺序来构建优先队列。
2. 根据数组queue的注释，我们可以知道，父节点与子节点的下标值之间的关联关系是：childLeftNode= 2 * parentNode + 1; childRightNode= 2 * (parentNode + 1);，那么根据当前结点计算父结点也很简单：parentNode = (thisNode - 1) / 2。

  Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)]. The priority queue is ordered by comparator, or by the elements natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

比如依次调用PriorityQueue的add方法，放入：3，5，7，1，9，12，18，7，6。画了一张图，大概如下：

优先队列数据

构造方法

了解了优先队列的大致结构及父子间关联关系之后，我们来看几个常用的构造方法。

/**
 * 默认构造方法，初始化容量为11，比较器为空
 */
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

/**
 * 指定具体容量的构造方法
 */
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) {
    // 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;
}

/**
 * 将集合转换为队列，根据集合类型不同，又分为三种情况
 */
public PriorityQueue(Collection<? extends E> c) {
    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<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}

还有几个构造方法是是实现方式和上面这几个差不多，就不一一贴上了。

方法

add方法

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方法内部全是通过offer方法来实现的，我们来看一下offer方法的大致实现过程：

1. 判空，添加数据不能为null；
2. 根据size与数组长度比较，判断是否扩容；
3. 判断添加的是不是第一个元素，如果不是，进行调整，增加完元素之后，我们需要进行调整才能维护最大堆或最小堆的性质。而这里的这个调整在堆中被称为上浮（对应的方法是siftUp）。

grow方法

那么我们就接着来看扩容方法grow。

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

扩容的时候，先判断当前队列容量是否<64，如果是扩容一倍容量，如果不是，扩容原容量的1/2。而hugeCapacity方法我们也看到多次了，参考List的扩容就知道了，就是溢出检查，而拷贝的方法也还是Arrays.copyOf方法。

siftUp方法

这个方法就是添加完元素之后进行的上浮调整方法。

private void siftUp(int k, E x) {
    // 是否有比较器
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

/**
 * 如果有比较器，调用该方法，内部实现和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;
}

/**
 * 如果没有比较器，调用该方法
 */
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    // k是下标值，保证结点有父级结点
    while (k > 0) {
        // 通过无符号右移，计算父级结点下标，-> parent = (thisNode -1) / 2
        int parent = (k - 1) >>> 1;
        // 获取父级结点的值
        Object e = queue[parent];
        // 比较要插入结点与父级结点值，如果大于父级结点，不需要移动，结束
        if (key.compareTo((E) e) >= 0)
            break;
        // 如果小于父结点值，父结点值上移，
        queue[k] = e;
        // 改变下标值
        k = parent;
    }
    // 最终将当前结点值放到对应的位置上
    queue[k] = key;
}

通过代码我们可以看到，调整的方式是判断是否有比较器，然后调用各自对应的处理方法。

1. 没有比较器，会按照我们添加的数据类型的比较器，也就是所谓的自然顺序来进行比较。比如说，我们添加的数据类型是int，那么这里会按照Integer的Comparable来进行排序；
2. 有比较器，按照对应的比较器的顺序来进行上浮操作。

由于画图工具太繁琐，操作流程可以参考网上的一个示例：

上浮操作

图片来源于：JDK源码研究PriorityQueue（优先队列)

peek方法和poll方法

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];
    // 将堆中最后一个值设置为null
    queue[s] = null;
    // 如果数组不是只有一个元素，执行下沉操作
    if (s != 0)
        // 下沉操作
        siftDown(0, x);
    return result;
}

  这两个都是出队的方法。其中，peek方法特别简单，就是取出堆中最小值元素，然后不移除数据，不用调整堆。
  而poll方法是取出堆中最小值的同时，移除该数据，同样，为了保证最小堆的性质，我们需要对堆进行另一种操作：下沉（siftDown）。

siftDown方法

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)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];
        // 右子结点等于左子结点下标加1
        int right = child + 1;
        // 如果左结点的值大于右结点，左结点赋值为右结点值
        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;
}

1. 先计算非叶子结点元素的最大位置；
2. 循环判断是否是叶子结点；
3. 计算根结点的左右子结点（也可以逻辑理解为将尾结点移动至根结点位置），然后循环比较根结点的左右子结点与尾结点值大小，直到尾结点的值小于其左右结点，或者尾结点处于叶子结点位置上时循环终止。

由于siftDownUsingComparator方法内部和siftDownComparable类似，就不解释了。

下沉操作

  当最小元素14出队，从数组尾处取39赋值给队首。之后，进行和增加元素后相反的动作即下沉。
  首先选出根节点（父节点）39的两个孩子结点中较小者，和39交换位置；当39找到新位置后，执行同种方法，如果孩子结点为null或者都比39大，则结束。

remove方法

public boolean remove(Object o) {
    //获取元素的下标    
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

/**
 * 执行移除操作
 */
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    // 如果要移除的就是最后一个元素，赋值为null
    if (s == i) // removed last element
        queue[i] = null;
    else {
        // 取队列尾元素
        E moved = (E) queue[s];
        // 将队尾元素置为null
        queue[s] = null;
        // 下沉操作
        siftDown(i, moved);
        // 如果下移后元素位置没发生变化，说明moved的左右子结点都大于moved，这时就需要上浮操作
        if (queue[i] == moved) {
            // 上浮操作
            siftUp(i, moved);
            // 如果上浮之后发生了元素位置
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

通过代码，我们可以知道remove方法是从队列中移除指定元素，如果该元素有不止一个，则移除数组中的一个出现的元素。

下沉操作 上浮操作

其他方法

/**
 * 查看是否包含，只需要拿indexOf的返回值和1进行比较即可
 */
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

/**
 * 获取元素的下标
 */
private int indexOf(Object o) {
    if (o != null) {
        // 循环遍历
        for (int i = 0; i < size; i++)
            // 调用equals方法进行比较
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

到这里，大部分方法都基本上分析完了。

总结

1. 优先队列是基于最小堆来实现的一种无界的队列，所以，队头出队的元素总是最小的。该队列不允许null元素，可以自定义优先级，也就是比较规则；
2. 该队列不是线程安全的，如果要在线程安全的场景下使用，建议使用线程安全的PriorityBlockingQueue类；

本文参考自：
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
JDK源码研究PriorityQueue（优先队列）