介绍

PriorityQueue，从类名我们也知道他是一个优先级队列。首先，作为队列，它具备队列的特征：①线性结构；②先进先出；③只允许在一端入队，另一端出队。但作为优先级队列时，队列中的每一个元素就有了优先级的属性，优先级越高的元素，越先出队，优先级越低的元素，越晚出队，而不再以先进先出的规则出队。就好比京海的几个小混混在排队买肠粉，这时唐小龙来了，那作为小弟自然要请唐小龙排在第一位；这时高启强又来了，作为唐小龙的大哥，自然也是要排在唐小龙前面的，于是买肠粉的队伍就发生了变化：肠粉店：小混混若干 变成了 肠粉店：唐小龙、小混混若干 变成了 肠粉店：高启强、唐小龙、小混混若干。

PriorityQueue的底层存储结构为默认初始容量为11的数组，在创建对象时可以指定初始容量。通过比较器和堆排序获取优先级最高的元素。不理解堆排序的朋友可以查看前面的文章：堆与堆排序。

强调：PriorityQueue是一个以优先级为出队规则的无界队列，通过自扩展的数组存储元素，通过堆排序算法获取优先级最高的元素。优先级越高越先出队。

构造函数

在PriorityQueue中，可供我们使用的构造方法较多，但细心的朋友会发现，实际上分为两种

通过指定参数实例化

// 无参构造，数组长度默认为11，比较器默认为null
public PriorityQueue() {
   
   
    this(DEFAULT_INITIAL_CAPACITY, null);
}

// 指定数组的初始长度，比较器默认为null
public PriorityQueue(int initialCapacity) {
   
   
    this(initialCapacity, null);
}

// 数组长度默认为11，指定比较器
public PriorityQueue(Comparator<? super E> comparator) {
   
   
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

// 指定数组的初始长度，指定比较器
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
   
   
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

在上面这四个构造方法中，都是围绕着初始容量和比较器这两个参数进行实例化的。

通过集合实例化

// 根据Collection集合对象来实例化PriorityQueue对象
public PriorityQueue(Collection<? extends E> c) {
   
   
    if (c instanceof SortedSet<?>) {
   
   
        // 如果参数为SortedSet类型的对象，先获取其比较器，再讲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);
    }
}

// 根据PriorityQueue对象来实例化PriorityQueue对象
public PriorityQueue(PriorityQueue<? extends E> c) {
   
   
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}

// 根据SortedSet集合对象来实例化PriorityQueue对象
public PriorityQueue(SortedSet<? extends E> c) {
   
   
    this.comparator = (Comparator<? super E>) c.comparator();
    initElementsFromCollection(c);
}

上面三个构造方法都是通过我们传入一个集合对象，实例化PriorityQueue对象。不难发现，无论我们传入的是PriorityQueue对象，还是SortedSet对象，他们其实都属于Collection对象，在实例化的过程中，其实只有两步：①获取比较器；②根据传入的参数初始化数组。

注意：在public PriorityQueue(Collection<? extends E> c)方法的最后一个代码块中，比较器comparator却是直接复制为null的，这是因为在Collection集合的大家族中，除了SortedSet和PriorityQueue内部有比较的功能从而具有比较器外，其他类是不存在比较器的。

三种队列初始化方法的比较

initElementsFromCollection()

从集合中初始化队列元素，不涉及堆化操作。

private void initElementsFromCollection(Collection<? extends E> c) {
   
   
    // 将集合转换成数组
    Object[] a = c.toArray();
    if (c.getClass() != ArrayList.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;
}

在此方法中，我们发现队列的初始化过程只是将参数转换成数组，然后添加元素的校验，并没有涉及到堆化，那么问题来了，在通过SortedSet集合实例化时，怎么确定队列已经堆化了呢？

其实这涉及到了SortedSet的知识点了，在这里简单说一下，SortedSet是一个有序的set集合，从名字也可以看得出来，既然说到有序，那么由SortedSet转换的数组自然也是有序的，而有序的数组时天然符合堆的定义的，因此无需进行额外的堆化操作。

initFromPriorityQueue()

从PriorityQueue类或其子类中初始化，如果是PriorityQueue类，则直接初始化队列元素；如果是其子类，则初始化队列元素后还需要进行堆化，以防不测。

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

此方法不难，如果传入的参数是PriorityQueue对象的话，直接将队列进行赋值操作即可，这种情况自然也是不用堆化的，但如果是PriorityQueue的子类的话，就要执行initFromCollection()方法。

initFromCollection()

从集合中初始化，该方法包含初始化队列元素、对队列中的元素堆化两个步骤。

private void initFromCollection(Collection<? extends E> c) {
   
   
    // 由集合初始化队列
    initElementsFromCollection(c);
    // 堆化
    heapify();
}

该方法相对于上面两个就比较通俗易懂了，就两步操作，

扩容原理

既然PriorityQueue是一个无界队列，且底层实现为数组，那么我们就有必要了解一下他是怎么扩容的，就像学习ArrayList扩容原理那样。

少废话，直接把源码贴上来：

private void grow(int minCapacity) {
   
   
    // 当前容量
    int oldCapacity = queue.length;
    // 新的容量
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 判断新容量的最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 数组拷贝，实例化新的数组作为底层数组
    queue = Arrays.copyOf(queue, newCapacity);
}

从源码中我们可以发现，PriorityQueue扩容的关键代码和ArrayList相同，都是通过Arrays类的copyOf()方法根据原数组和新容量构造一个新的数组。

不同之处在于PriorityQueue扩容时相比ArrayList少了很多判断，这是因为在ArrayList中我们可以通过public void ensureCapacity(int minCapacity)主动扩容，因此ArrayList添加了许多判断来避免各种异常的发生；而PriorityQueue的扩容时被动的，只有我们向队列中添加元素时，才会判断是否需要扩容，因此避免了各种判断。

另一个不同之处在于扩容时的增量大小，我们都知道ArrayList扩容时新容量为原容量的1.5倍；而PriorityQueue中分两种情况：①若原容量小于64，则新容量 = 2 * 原容量 + 2；②否则，新容量 = 原容量 * 1.5。

向上调整

当我们需要向堆中插入一个元素时，往往是先将待操作元素放在队尾，然后根据堆的定义，将待操作元素与父元素比较，根据比较结果决定是否将待操作元素与父元素互换位置，如果需要互换位置，则在互换之后再次将待操作元素与新的父元素继续比较，如此循环往复，直到根节点位置；如果不需要互换位置，则终止循环。这个过程就是向上调整了。

我们看一下在PriorityQueue中向上调整的源码：

// 向上调整，
// k-从队列中下标为k的位置开始调整
// x-待操作元素
// siftUpUsingComparator方法和siftUpComparable方法的不同之处是：
// 一个使用Comparator的compare()方法进行比较，另一个使用Comparable接口定义的compare()方法进行比较
private void siftUp(int k, E x) {
   
   
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

// 我们以siftUpComparable()方法为例
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;
    }
    // 将待操作元素e放置在队列中下标为k的位置
    queue[k] = key;
}

向下调整

当我们要删除一个元素时，队列中待删除元素前面的元素应该是不允许调整的，如果将前面的元素调整至待删除元素的位置，虽然待删除元素后面的元素依然满足堆的定义，但是其前面的元素出现了空缺，不符合完全二叉树的定义更不符合堆的定义。因此正确的做法是将队列中最后一个元素放在待删除元素的位置上，即覆盖。然后从此位置开始逐步向下调整。

在调整的过程中，以小顶堆为例，首先获取当前下标的左右两个孩子并比较出两者的较小值，如果右孩子不存在，则左孩子元素为较小值，如果孩子元素的较小值比当前元素小，则将较小值与当前下标元素互换，并将当前下标向下调整到较小值的下标，否则停止向下调整。以此循环，直到当前元素不再存在孩子元素。

// 向下调整，
// k-从队列中下标为k的位置开始调整
// x-待操作元素
private void siftDown(int k, E x) {
   
   
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

private void siftDownUsingComparator(int k, E x) {
   
   
    // 将队列长度size向右移一位，即size/2的值向下取整
    int half = size >>> 1;
    while (k < half) {
   
   
        // 1 获取下标为k的元素的左右孩子中较小的孩子c，以及对应的下标child
        // 1.1 获取下标为k的元素的左孩子c，并假设c为左右孩子的较小元素
        int child = (k << 1) + 1;
        Object c = queue[child];

        // 1.2获取下标为k的元素的右孩子right
        int right = child + 1;

        // 1.3如果存在右孩子，且右孩子比左孩子小
        // 则将右孩子作为最小元素，右孩子下标为最小元素下标
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];

        // 2 如果下标为k的元素 > 待操作元素，则结束循环
        if (comparator.compare(x, (E) c) <= 0)
            break;

        // 3 将较小的孩子c放置在下标为k的元素上，下标k向下调整至原较小孩子的坐标
        queue[k] = c;
        k = child;
    }
    // 将待操作元素放置在下标为k的元素上。
    queue[k] = x;
}

堆化

堆化的过程就是将一个序列根据关键字转换成大顶堆或小顶堆的过程。其中涉及到向上调整和向下调整。我们来看一下PriorityQueue的源码来学习它的堆化过程。

private void heapify() {
   
   
    // (size >>> 1) - 1 的值为非叶子结点的最大下标
    // 从最后一个非叶子结点开始，逐步向根结点循环遍历
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        // 以当前结点下标和当前元素为参数，向下调整
        siftDown(i, (E) queue[i]);
}

用一句话总结堆化的过程就是：从最大非叶子结点开始向上调整，在每一次调整的过程中，都以当前非叶子结点为准向下调整。

注意：堆化后的序列只能保证堆顶元素为最大值或最小值，并不保证整个序列的有序性。

常用方法

public boolean add(E e)

向队列中添加一个元素，继承于AbstractQueue抽象类，重写了抽象类的实现，但差别不大。
public boolean offer(E e)

入队，继承于Queue接口，该方法主要行为：①判空；②扩容；③向上调整。
public E peek()

查看队列头元素，但不出队
public boolean remove(Object o)

删除队列中与参数oequals()判断结果为true的元素，该方法主要行为：①找到队列中目标元素的下标；②删除该元素并根据情况作出向上调整和向下调整
public boolean contains(Object o)

根据equals()方法判断队列中是否存在于参数o相同的元素，如果有，则返回true，否则false
public Object[] toArray()

将队列转换成数组，通过Arrays.copyOf()方法实现
`public T[] toArray(T[] a)``

将队列中的元素放置在数组a中，通过Arrays.copyOf()方法实现
public int size()

获取队列中元素数量
public void clear()

将队列中的所有元素全都置为null
public E poll()

出队。主要行为：向下调整。
public Comparator<? super E> comparator()

获取比较器。

总结

队列的默认初始容量为11
队列扩容时，如果原容量小于64，则新容量为原容量的2倍，否则，新容量为原容量的1.5倍
元素不能为空。因为在比较大小时需要调用元素对象的compare方法。
线程不安全。通篇源码中未发现加锁行为。
无界。最大上限为最大整数
底层的物理结构为数组，逻辑结构为堆
必须指定一个Comparator自然比较器并实现对应的compare()方法；或队内元素必须实现Comparable接口并实现对应的compare()方法

PriorityQueue源码详解

目录

介绍