队列概述

1.基于优先堆得无界队列（初始默认长度11，最大长度Integer.MAX_VALUE - 8;），容量会自动增长。
2.根据自然顺序、队列构造时提供的Comparator排序。
3.不允许插入null、不可比较元素，线程不安全。（PriorityBlockingQueue线程安全）
4.最小元素存放在队头。（如果并列最小，则随机存放）。
5.队列检索操作poll ， remove ， peek和element访问队列开头的元素
6.时间复杂度分析
入队和出队方法（ offer ， poll ， remove()和add ）提供O（log（n））时间； remove(Object)contains(Object)方法的线性时间；
固定时间的检索方法（ peek ， element和size ）

一、队列基本信息

1.队列继承关系图

2.重要属性

    /**
     *指定队列默认长度（初始化，不指定队列长度时，采用此值）
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    /**
     *底层存储元素数组。transient标记数组不会被序列化
     */
    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.
     * 如果为null，则使用自然排序。（初始化时，可以指定比较器）
     */
    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
    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     * 指定队列存储的最大元素个数
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

二、源码分析

    /**
    * 可指定比较器的构成函数
    */
    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;
    }
    /**
    *通过传递集合入参，初始化队列
    * 1.入参为SortedSet
    * 2.入参为队列
    * 3.入参为其他集合类型
    */
    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);
        }
    }
    /**
    * 通过【有序集合】进行队列元素初始化
    * 1.将集合处理为Object[]类型
    * 2.校验集合中是否存在null元素，如果存在则报错
    * 3.将1中数组赋值队列中数据对象
    */
    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        // If c.toArray incorrectly doesn't return Object[], copy it.
        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++)//队列中不允许存储null值
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }
    /**
     * Initializes queue array with elements from the given Collection.
     * 1.初始化底层数组
     * 2.对数组进行排序
     * @param c the collection
     */
    private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }
    private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }
    /**
    *排序，利用数组实现二叉堆排序（可参考PriorityBlockingQueue队列）
    */
    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];
            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;
    }