jdk1.8源码阅读PriorityQueue

package java.util;

import java.util.function.Consumer;

/**
 * 优先队列，在队列里的顺序会按照指定的Comparator对象进行比较，
 * 元素按照优先级高低进行排列，实现方式是平衡二叉堆,平衡二叉堆分为
 * 大顶堆和小顶堆，此类实现是使用的小顶堆，可以重写元素的compareTo
 * 方法或者重写Comparator接口的compare方法实现大顶堆
 */
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    private static final long serialVersionUID = -7720805057305804111L;

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     *使用Object[]数组存放队列，将数组看做一个完全二叉树结构,则queue[n]的左孩子和
     *右孩子分别为queue[2*n+1]和queue[2*(n+1)],并且需要满足父节点比孩子节点的优先级高
     *
     */
    transient Object[] queue; // non-private to simplify nested class access

    /**
     * 队列大小
     */
    private int size = 0;

    /**
     * 元素比较对象，如果为空则使用元素自然排序,其中comparator限定了E或者
     * E的父类实现了Comparator接口
     */
    private final Comparator<? super E> comparator;

    /**
     * 优先队列修改次数
     */
    transient int modCount = 0; // non-private to simplify nested class access

    /**
     * 初始化一个默认大小的队列，排序使用元素自然排序
     */
    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;
    }

    /**
     * 初始化一个集合对象做为优先队列，传入的collection参数类型是E或者E的子类
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(Collection<? extends E> c) {
        //如果c是SortedSet对象，则将SortedSet对象的排序方式赋值给优先队列的排序方式
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            //将SortedSet的比较器赋值给PriorityQueue的比较器
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        //如果c是优先队列，同上
        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);
        }
    }

    /**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified priority queue.  This priority queue will be
     * ordered according to the same ordering as the given priority
     * queue.
     *
     * @param  c the priority queue whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of {@code c} cannot be
     *         compared to one another according to {@code c}'s
     *         ordering
     * @throws NullPointerException if the specified priority queue or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }

    /**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified sorted set.   This priority queue will be ordered
     * according to the same ordering as the given sorted set.
     *
     * @param  c the sorted set whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of the specified sorted
     *         set cannot be compared to one another according to the
     *         sorted set's ordering
     * @throws NullPointerException if the specified sorted set or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }

    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }

    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();   //将c转化为Object[]数组
        // 如果c不是Object[]数组则转化为Object
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;

        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null) 
                    throw new NullPointerException();
        this.queue = a; //将数组赋值给队列
        this.size = a.length; //修改大小
    }

    /**
     * 将集合对象初始化为优先队列
     */
    private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }

    /**
     * 数组最大值，Integer最大值减8,int最大值是2^31 - 1
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
    * 增加数组容量
     */
    private void grow(int minCapacity) {

        //获取队列的容量
        int oldCapacity = queue.length;
        // 如果队列容量小于64，则新容量为2倍的旧容量+2，如果大于64则新容量为
        //旧容量的3倍
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // 如果超过了数组最大限制，则调用hugeCapacity获取最大容量
        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();
        //如果超过数组最大限制则返回Integer的最大值，否则返回数组最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    /**
     * 向优先队列添加一个元素
     */
    public boolean add(E e) {
        return offer(e);
    }

    /**
     * 向优先队列添加一个元素
     */
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;  //修改次数+1
        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;
    }

    /**
     * 获取队头元素
     */
    @SuppressWarnings("unchecked")
    public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }

    //获取o第一次出现在队列中的位置
    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

    /**
     *移除指定元素
     */
    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

    /**
     * 移除第一次在队列中出现的元素
     */
    boolean removeEq(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    /**
     *判断队列是否包含元素o
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    /**
     * 将队列复制为一个Object数组
     */
    public Object[] toArray() {
        return Arrays.copyOf(queue, size);
    }

    /**
     * 将队列复制为一个指定类型的数组
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        final int size = this.size;
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(queue, size, a.getClass());
        System.arraycopy(queue, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    /**
     * 获取一个队列迭代器
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     *  迭代器实现，由于是优先队列，要保持二叉堆的性质，所以在迭代过程
     *中如果删除某元素可能会导致已经遍历的过得元素，移动到了被删除位置，末尾元素
     * 被移动到了已经遍历过的位置。所以需要额外存储这些未遍历到但是移动到已经遍历
     * 过的位置的元素。
     */
    private final class Itr implements Iterator<E> {
        /**
         * 队列当前游标
         */
        private int cursor = 0;

        /**
         * 上一次遍历到队列的位置
         */
        private int lastRet = -1;

        /**
         * 在用iterator迭代过程中，如果有删除操作，会将末尾元素放到被删除位置进行调整，维持二叉堆的性质
         * 如果元素被调整到被删除位置的上方，则将此元素加入双端队列，因为末尾的元素被删除，并且调整到的位置
         * 已经遍历过了，所以为了防止遍历不到此元素，就会加入双端队列，对数组遍历完之后，就会对双端队列进行
         * 遍历
         */
        private ArrayDeque<E> forgetMeNot = null;

        /**
         * 使用
         */
        private E lastRetElt = null;

        /**
         * 期望修改次数初始化为实际修改次数
         */
        private int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor < size ||
                (forgetMeNot != null && !forgetMeNot.isEmpty());
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
            //队列本身没迭代完，则输出队列的元素
            if (cursor < size)
                return (E) queue[lastRet = cursor++];
            //如果双端队列不为空，从队列输出元素
            if (forgetMeNot != null) {
                lastRet = -1;
                lastRetElt = forgetMeNot.poll();
                if (lastRetElt != null)
                    return lastRetElt;
            }
            throw new NoSuchElementException();
        }

        public void remove() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
            if (lastRet != -1) {
                E moved = PriorityQueue.this.removeAt(lastRet);
                lastRet = -1;
                //如果没被调整到lastRet的上方，则游标需要重新置为上次遍历的位置
                if (moved == null)
                    cursor--;
                else { //如果moved不为空说明调整到了lastRet的上方，则需要将moved加入到双端队列
                    if (forgetMeNot == null)
                        forgetMeNot = new ArrayDeque<>();
                    forgetMeNot.add(moved);
                }
            } else if (lastRetElt != null) { //如果移除的是双端队列的元素，则调用removEq
                PriorityQueue.this.removeEq(lastRetElt);
                lastRetElt = null;
            } else {
                throw new IllegalStateException();
            }
            expectedModCount = modCount; //重新给期望修改值赋值
        }
    }

    //获取队列大小
    public int size() {
        return size;
    }

    /**
     *清空队列，对数组的每个元素都置为null
     */
    public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            queue[i] = null;
        size = 0;
    }

    /**
     * 获取队头元素，并且移除队头元素
     */
    @SuppressWarnings("unchecked")
    public E poll() {
        //如果队列为空则返回空
        if (size == 0)
            return null;
        //获取最后一个结点的位置，并且队列大小减一
        int s = --size;
        //修改次数加一
        modCount++;
        //获取队列头元素
        E result = (E) queue[0];
        //获取队尾元素
        E x = (E) queue[s];
        //队尾置为空
        queue[s] = null;
        //如果队列不为空，则向下调整二叉堆，这个不需要向上调整，因为位置0是根节点
        if (s != 0)
            siftDown(0, x);
        return result;
    }

    /**
     * 移除位置i的元素，在调整堆的时候如果最后一个元素被调整到位置i的上方
     * 则返回最后一个元素，否则返回null
     */
    @SuppressWarnings("unchecked")
    private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;   //修改次数加一
        int s = --size; //最后一个元素的位置，并且队列容量减一
        if (s == i) //如果要移除的元素是最后一个元素则直接最后一个元素置空
            queue[i] = null;
        else {
            E moved = (E) queue[s];//获取最后一个元素
            queue[s] = null; //最后一个元素的位置置空
            siftDown(i, moved); //将最后一个元素插入位置i并对堆做向下调整
            //向下调整完，如果位置i的元素和最后一个元素相等，说明向下调整时
            //各个元素的位置都没发生改变，说明i的孩子结点都符合堆的性质，然后
            //需要向上做调整，看i的父节点是否满足堆的性质
            if (queue[i] == moved) {
                //向上调整
                siftUp(i, moved);
                //说明moved被调整到了i的上方，则返回moved，Iterator迭代器会使用这个结果
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

    /**
     * 从下往上调整
     */
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
      /**
     * 从下往上调整
     */
    @SuppressWarnings("unchecked")
    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上升到父结点
            k = parent;
        }
        queue[k] = key;
    }

    /**
     * 新插入的元素从下往上调整，满足二叉堆的性质
     */
    @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;
    }

    /**
     * 新插入的元素从上往下调整，满足二叉堆的性质
     */
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

    @SuppressWarnings("unchecked")
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        //half为第一个叶子节点
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1; // 左孩子位置
            Object c = queue[child]; //左孩子值
            int right = child + 1; //右孩子位置
            //找到左孩子和右孩子中的较小的
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            //如果key小于最小的，则直接退出循环，说明此结点满足二叉堆规则
            if (key.compareTo((E) c) <= 0)
                break;
            //将最小的赋值给位置k
            queue[k] = c;
            k = child;  //将最小位置的位置赋值给k，进行下次循环
        }
        queue[k] = key;//将x赋值给最后迭代到的k位置queue[k]
    }

    //
    @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]; //找出最小的结点，并且将最小位置赋值给child
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;//将最小值赋值给queue[k]
            k = child; //将最小值位置赋值给k，做下次迭代
        }
        queue[k] = x; //将x赋值给最后迭代到的k位置queue[k]
    }

    /**
     * 将queue数组初始化为二叉堆.
     */
    @SuppressWarnings("unchecked")
    private void heapify() {
        //从尾结点的父节点开始调整
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

    /**
     * 返回比较器对象
     */
    public Comparator<? super E> comparator() {
        return comparator;
    }
}