PriorityQueue一行代码引发的思考

昨天看到一篇文章介绍延时队列，其中有个方案是利用JDK自带的DelayQueue，所以就看一下其源码。

PriorityQueue

DelayQueue的功能就是当一个元素的延期时间到期时才会返回这个元素。初步看到源码，发现有个成员变量PriorityQueue：

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {

    private final transient ReentrantLock lock = new ReentrantLock();
    private final PriorityQueue<E> q = new PriorityQueue<E>();

大概介绍一下PriorityQueue的功能：就是入队的每个元素都有一个分数，队列根据分数的大小排序，保证每次出队元素的分数是队列中最小的。
于是点开PriorityQueue源码，先比较重要的是4个成员变量：

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+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.
     */
    transient Object[] queue; // non-private to simplify nested class access

    /**
     * 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; // non-private to simplify nested class access

queue：存放入队元素信息
size：存放队列长度信息
comparator：如果传入则采用比较器的逻辑来比较两个元素的大小
modCount：记录队列被修改的次数，用来限制并发修改。

现在看一下当一个元素被加入队列之后是如何排序的，插入元素的方法有两个add(E e)，offer(E e)：

public boolean add(E e) {
        return offer(e);
    }

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    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;
    }

可以看到先判断队列长度如果已达到最大长度则需要调用grow()扩容，然后如果不是第一个元素则要调用siftUp(int k, E x)方法进行排序：

  /**
     * Inserts item x at position k, maintaining heap invariant by
     * promoting x up the tree until it is greater than or equal to
     * its parent, or is the root.
     *
     * To simplify and speed up coercions and comparisons. the
     * Comparable and Comparator versions are separated into different
     * methods that are otherwise identical. (Similarly for siftDown.)
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

这里看到有个排序逻辑的判断，如果实例化队列的时候指定了比较器则优先使用比较器，如果没有则使用元素本身的比较逻辑，这里也要求队列中的元素要实现Comparable<T>接口。这里拿元素自身比较逻辑举例，所以继续分析siftUpComparable(int k, E x)方法， siftUpUsingComparator(int k, E x)的逻辑与其相同：

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) 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;
    }

其中k是希望要插入的位置，x是待插入的元素。如果k<0则说明队列中无元素，所以直接插入，如果k>0则需要判断x（待插入的元素）和parent中的元素（位置k的父节点）哪个小，两者较大的元素放置在k位置、较小的放置到parent位置。如果是x较小，再用x（此时已经在parent位置）与其父节点的元素进行上述比较并执行相同的逻辑，直到比下一个父节点元素大为止。这个数据结构也叫做“最小堆”。

举个例子

image.png

上面这个图是计算机利用数组实现二叉树的逻辑，其中相同颜色表示数组存储的二叉树的哪个元素。由图上可知，下一个要插入的元素在数组中的索引是6，在二叉树中是在没有颜色的位置。但是在“最小堆”的约束中，它不一定是在没有颜色的那个位置，如果它比蓝色节点的元素要小的话，他们两个就要互换位置并且继续和绿色元素比较，如果比绿色元素小同样也要互换位置。

一行代码

第一眼看到这个代码的时候觉得比较神奇，就是下面代码：

 int parent = (k - 1) >>> 1;

用一行代码就找到了元素的父节点，而且不考虑左节点和右节点，有点厉害，是什么原理呢？

数学依据

这里要用到一些二叉树的性质：

第n层的二叉树有2^(n-1)个节点。这个可以用等比数列的公式证明，例如：第一层有2^0个，第二层有2^1个，第三层有2^2个。
处于第n层的第m个元素之前有2^n+m-1。这个可以用等比数列的求和公式证明，至于二叉树可以用更直观的方式证明，二叉树的每一层其实就是二进制的每一位，第一层最大是1，前两层最大可以表示3（二进制11），前三层最大是7（111）,那第四层按照第一点可以证明是有8个节点（1000），其实就是111+1=1000。所以第n层之前总共有2^n-1个节点，那在n+1层的m个节点时，总共有2^n+m-1个节点。

image.png

一个节点在本层的位置是m，那么他的子节点在下一层的位置应该是2m-1、2m，所以到这两个子节点时，总共有2^(n+1)-1+2m和2^(n+1)-1+2m-1= 2^(n+1)+2m-2个节点。
所以，父节点序号：2^n+m-1，子节点序号：2^(n+1)-1+2m、2^(n+1)+2m-2。
因为是用数组实现的，所以第一个索引为0，因此上述序号都要减一：

父节点下标：2^n+m-2
左子节点下标：2^(n+1)+2m-3
右子节点下标：2^(n+1)+2m-2

得出结论：子节点的下标除以父节点的下标可以得到他们之间的关系，左右子节点下标为： 2K+1、2K+2，其中k是父节点的下标值。

代码实现

如果得到子节点的下标，依据上述结论，减一或者减二再除以2就可以得到父节点的下标，那么如何做到呢？这个时候要看看>>>这个操作符了，它表示带符号位往右平移某几位，例如：0100 >>> 2 =0001。它有个特征，就是会抹去最右边几位的数值，因为右移之后超出范围的数值会被舍弃。所以再回过头来看那一行代码：

 int parent = (k - 1) >>> 1;

k有两种情况：

偶数：说明即将插入的是右节点。需要(k-2)/2来得出父节点的下标。此时的k是右子节点下标。
奇数：说明即将插入的是左节点。需要(k-1)/2来得出父节点的下标。此时的k是左子节点下标。

这时可以看到，如果是奇数（左节点）的话完全可以用(k - 1) >>> 1实现，如果是偶数（右节点）在执行完(k - 1)后，因为最右一位是1（此时变为奇数），所以在>>>1的时候会自动抹去最右一位，也就是额外减去一，实际效果和k-2是一样的。

这样就可以用一行代码来处理两种不同的数学逻辑，豁然开朗！