优先级队列（PriorityQueue）

队列就是一种先进先出的数据结构，优先级队列就是在队列的基础上增加了对其中的数据增加了优先级这种情况，在某些特定的情况下，我们需要对优先级高的数据进行出队列。

优先级队列（PriorityQueue）

优先级队列在集合框架中的位置，从图中，可以清楚的知道，PriorityQueue是一个类，并且继承Queue这个接口

对于这种数据结构，我们需要注意的是

• 插入的数据必须要可以进行大小的比较，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
• 不能插入null对象，否则会抛出NullPointerException
• 没有容量的一个限制，其底层可以自动的进行扩容
• 插入和删除数据元素的时间复杂度为O($log_{2} N$log2​N)
• PriorityQueue其底层使用了堆这种数据结构

1、常用接口
优先级队列的构造

插入、删除、获取优先级最高元素

注意：扩容机制（JDK1.8）

 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 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时，是按照oldCapacity*2 + 2的方式扩容的
• 如果容量大于等于64，是按照oldCapacity*2的方式扩容的
• 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容