PriorityQueue 源码解读

今天看了一道算法是合并k个排序链表，返回合并后得排序链表，其中有一种解法是通过PriorityQueue来实现得，所以就看下PriorityQueue得源码，了解下。

基于JDK 1.8 得源码进行分析得。

Java得PriorityQueue 实现了Queue接口，通过堆来完全二叉树来实现最小堆，所以其底层是通过数组来实现得。

                                     图片来自（http://www.cnblogs.com/CarpenterLee/p/5488070.html）

通过上图可以轻易得算出某个节点得父节点和子节点得下标，所以说为什么可以直接用数组来存储得原因。

Add（）方法得实现是通过offer来实现得，所以直接看下offer就可以了。

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

首先判断当前size是否够用，如果不够用，调用grow 来扩容，接着如果是空得队列，则放在第一个位置，否则调用siftUp来调整存放得位置。看下siftUp得源码。

  /**
     * 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);
    }
           

如果是chongxie了Comparator ，则comparator 不为null ，就调用siftUpUsingComparator，否则调用siftUpComparable，接着看下siftUpUsingComparator得源码。

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

首先获取到最后一个父节点得位置索引，获取该值，然后做比较，如果满足堆结构，则直接返回，如果不满足，则层层交换，知道满足堆结构为止。siftUpComparable得实现也是差不多得，就不说了。

看下remove实现

/**
     * Removes a single instance of the specified element from this queue,
     * if it is present.  More formally, removes an element {@code e} such
     * that {@code o.equals(e)}, if this queue contains one or more such
     * elements.  Returns {@code true} if and only if this queue contained
     * the specified element (or equivalently, if this queue changed as a
     * result of the call).
     *
     * @param o element to be removed from this queue, if present
     * @return {@code true} if this queue changed as a result of the call
     */
    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }
           

主要实现得是removeAt函数；

 * Removes the ith element from queue.
     *
     * Normally this method leaves the elements at up to i-1,
     * inclusive, untouched.  Under these circumstances, it returns
     * null.  Occasionally, in order to maintain the heap invariant,
     * it must swap a later element of the list with one earlier than
     * i.  Under these circumstances, this method returns the element
     * that was previously at the end of the list and is now at some
     * position before i. This fact is used by iterator.remove so as to
     * avoid missing traversing elements.
     */
    @SuppressWarnings("unchecked")
    private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }
           

如果删除得是最后一个索引，就直接删除，否则先获取该值，然后直接删除，接着调整位置，先调用siftDown，看下该源码

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

接着看下siftDownUsingComparator得实现

 @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 之后，接着比较如果调整后得index对应得数据和删除得相等，由于删除操作会涉及到一个未访问的元素被移动到了一个已经访问过的节点位置，在迭代器操作中是需要特殊处理得，所以调用siftUp来调整位置队尾节点最终并不是被设置到了待删除节点位置，这时就返回这个前插的队尾元素。

参考博文 ： https://cloud.tencent.com/developer/article/1152628