前言

---

 相关系列

• 《Java ~ Collection【目录】》（持续更新）
• 《Java ~ Executor【目录】》（持续更新）
• 《Java ~ Collection/Executor ~ PriorityBlockingQueue【源码】》（学习过程/多有漏误/仅作参考/不再更新）
• 《Java ~ Collection/Executor ~ PriorityBlockingQueue【总结】》（学习总结/最新最准/持续更新）
• 《Java ~ Collection/Executor ~ PriorityBlockingQueue【问题】》（学习解答/持续更新）

 涉及内容

• 《Java ~ Collection【总结】》
• 《Java ~ Collection ~ Queue【总结】》
• 《Java ~ Collection/Executor ~ BlockingQueue【总结】》
• 《Java ~ Executor【总结】》
• 《Java ~ AQS ~ ReentrantLock【总结】》
• 《Java ~ Other ~ Comparator【总结】》
• 《Java ~ Other ~ Comparable【总结】》

一 概述

---

 简介

    PriorityBlockingQueue（优先级阻塞队列）类是BlockingQueue（阻塞队列）接口的实现类之一，基于数组实现。优先级阻塞队列类不是标准的FIFO队列，元素会以小顶堆的规则被排序并存放在数组的相应位置中。因此，当在实际开发中对元素的顺序有特定要求时，可以使用优先级阻塞队列类。所谓的小顶堆本质是一类特殊的完全二叉树，其规则是父元素一定小于/等于两个子元素（子元素之间不要求大小比对）。类似的，当父元素大于/等于两个子元素时，就是所谓的大顶堆。在优先级阻塞队列类中，小顶堆以数组的形式保存。之所以可以使用数组来模拟小顶堆，是因为元素索引会以以下规则分布在数组上：

左/右子元素索引 = 2 * 父元素索引 + 1/2

    优先级阻塞队列类必须定义比较器或元素必须实现比较能力。优先级阻塞队列类是具备排序能力的队列，而众所周知比较是排序的基础条件，为了实现这一点，优先级阻塞队列类设计了两种方式进行元素间的比较：一是使用比较器，即Comparator（比较器）接口对象；二是通过元素自身的比较能力，即元素类必须实现Comparable（比较能力）接口。开发者必须至少实现两者当中的一个，否则将会在使用过程中抛出类转换异常。比较器相比比较能力而言拥有更高的优先级，通俗的说就是当两种比较方式都满足的情况下会优先使用比较器进行比较。

    延迟队列类是无界队列，意味着其最大容量理论上只受限于堆内存的大小。延迟队列类底层使用优先级队列类实现，由于其扩容机制的存在，延迟队列类也被纳入无界队列的范围中。但虽说如此，优先级队列类在实现中还受到数组实现与int类型影响，因此延迟队列的最大容量实际上为Integer.MAX_VALUE。由于其无界队列的定义，为了掩盖实际实现中受到的限制，当其保存的元素总数触达上限时会模拟堆内存不足的场景手动抛出内存溢出错误。

    优先级阻塞队列类是真正意义上的无界队列，即容量理论上只受限于堆内存的大小。基于数组实现的原因及出于节省内存的目的，优先级阻塞队列类内部存在扩容机制，以使得元素数组的长度能够更加贴合实际所需，故而优先级阻塞队列类存在初始容量的说法，可在创建时显式指定。如果在创建优先级阻塞队列时未显式指定初始容量，则会隐式设置其为默认初始容量11。当元素总数触达优先级阻塞数组的当前容量时会触发扩容。扩容的本质是创建长度更大的新元素数组来代替旧元素数组，并将旧元素数组中的元素迁移至新元素数组。容量的具体增长规则如下：

旧容量 < 64：新容量 = 旧容量 * 2 + 2（快速成长）

旧容量 >= 64：新容量 = 旧容量 + 旧容量 >> 1（约1.5倍）

    由于在具体实现上受到int类型的物理限制，因此虽说优先级阻塞队列类是无界队列，但实际最大容量仅可扩容至Integer.MAX_VALUE - 8。减8的原因是因为有些虚拟机会在数组中保存源数据（header words），故而特意留出了这部分空间。但话虽如此，优先级阻塞队列最多依然可能保存Integer.MAX_VALUE个元素。因为优先级阻塞队列类虽然限制了通过常规单插入使得容量超过Integer.MAX_VALUE - 8的可能，但却可以通过批量插入来突破这个限制。为了兼容使用元素总数超过Integer.MAX_VALUE - 8的集进行批量插入及创建优先级阻塞队列的情况，优先级阻塞队列类是允许这么做的，但后果是可能抛出内存溢出错误。

    优先级阻塞队列类不允许存null，或者说阻塞队列接口的所有实现类都不允许存null。null被poll()及peek()方法作为优先级阻塞队列不存在元素的标记值，因此所有的阻塞队列接口实现类都不允许存null。

    优先级阻塞队列类是线程安全的，或者说阻塞队列接口的所有实现类都是线程安全的，其接口定义中强制要求实现类必须线程安全。优先级阻塞队列类采用“单锁”线程安全机制，即使用单个ReentrantLock（可重入锁）锁来保证整体的线程安全。但与此同时其还添加了“无锁”线程安全机制来辅助扩容，即在元素数组扩容时使用CAS乐观锁保证线程安全的同时不阻塞移除方法的执行，该知识点会在下文详述。由于CAS乐观锁并不是真正意义上的锁，因此被称为“无锁”线程安全机制。

    优先级阻塞队列类的迭代器是弱一致性的，即可能迭代到已移除的元素或迭代不到新插入的元素。优先级阻塞队列类的迭代器实现非常直接（或者说归于直接了），其会直接将数据拷贝一份快照存入生成的迭代器中以进行迭代。这么做的好处是迭代器的实现非常的简单，但缺点也明显，当优先级阻塞队列的元素总数较大或生成的迭代器数量较多时对内存的消耗会非常严重。优先级阻塞队列类使用快照来实现迭代器的原因是元素会因为排序而难以追踪其位置上变化，因此使用不变的快照是最好的做法。

    优先级阻塞队列类虽然与阻塞队列接口一样都被纳入Executor（执行器）框架的范畴，但同时也是Collection（集）框架的成员。

 结构

 方法的不同形式

    方法的不同形式实际上是BlockingQueue（阻塞队列）接口的定义，优先级阻塞队列类只是继承了这个定义而已。所谓方法的不同形式，是指方法在保证自身核心操作不变的情况下实现了多种不同的回应形式来应对不同场景下的使用要求。例如对于插入，当容量不足时，有些场景希望在失败时抛出异常；而有些场景则希望能直接返回失败的标记值；而有些场景又希望可以等待直至有可用空间后成功新增为止…正因如此，BlockingQueue（阻塞队列）接口特意提供了四种不同的形式风格以满足不同场景下的使用需求，因此一个方法最多（并非所有方法都实现了四种形式）可能有四种不同回应形式。具体四种回应形式如下：

异常 —— 队列接口定义 —— 当不满足操作条件时直接抛出异常；
特殊值 —— 队列接口定义 —— 当不满足操作条件时直接返回失败标记值。例如之所以不允许存null值就是因为null被作为了操作失败时的标记值；
阻塞（无限等待） —— 阻塞队列接口定义 —— 当不满足操作条件时无限等待，直至满足操作条件后执行；
超时（有限等待） —— 阻塞队列接口定义 —— 当不满足操作条件时有限等待，如果在指定等待时间之前满足操作条件则执行；否则返回失败标记值。

二 创建

---

• public PriorityBlockingQueue() —— 创建默认初始容量（11）的优先级阻塞队列。

• public PriorityBlockingQueue(int initialCapacity) —— 创建指定初始容量的优先级阻塞队列。

• public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) —— 创建指定初始容量及比较器的优先级阻塞队列。

• public PriorityBlockingQueue(Collection<? extends E> c) —— 创建按指定集比较器/能力顺序包含指定集中所有元素的优先级阻塞队列。
      如果指定集是SortedSet（排序集合）接口对象或者优先级阻塞队列，方法首先会获取其比较器，并在比较器存在的情况下将之用于对指定集中的元素进行排序；否则通过指定集中元素的比较能力进行排序。因此在指定集无法获取比较器的情况下，其内部元素必须是比较能力接口对象。为了保证元素在优先级阻塞队列中按比较器/能力顺序排序，方法会在不确定元素数组符合要求的情况下对之进行堆化处理。堆化的本质是批量下排序，该知识点会在下文详解。

/**
 * Creates a {@code PriorityBlockingQueue} containing the elements in the specified collection.  If the specified collection is a {@link SortedSet}
 * or a {@link PriorityQueue}, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered
 * according to the {@linkplain Comparable natural ordering} of its elements.
 * 创建一个包含指定集中元素的优先级阻塞队列。如果指定集是一个排序集合或者优先级队列，该优先级队列将按相同的顺序进行排序。否则该
 * 优先级队列将根据元素的比较能力进行排序（因此在元素在优先级阻塞队列中的排序可能与指定集中的不同）。
 *
 * @param c the collection whose elements are to be placed into this priority queue  集中的元素将存放与优先级队列
 * @throws ClassCastException   if elements of the specified collection cannot be compared to one another according to the priority queue's
 *                              ordering
 *                              如果指定集的元素无法与根据优先级队列的顺序进行比较（如果有某个元素没有实现比较能力接口就会出现）
 * @throws NullPointerException if the specified collection or any of its elements are null
 *                              空指针异常：如果指定集或集中的任意元素为null
 */
public PriorityBlockingQueue(Collection<? extends E> c) {
    // 实例化所与条件。
    this.lock = new ReentrantLock();
    this.notEmpty = lock.newCondition();
    // true if not known to be in heap order
    // 如果不知道堆顺序，则为true
    boolean heapify = true;
    // true if must screen for nulls
    // 如果必须筛选空值，则为true
    boolean screen = true;
    if (c instanceof SortedSet<?>) {
        // 如果指定集是一个排序集合，则将排序集合的比较器作为优先级阻塞队列的比较器。
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        heapify = false;
    } else if (c instanceof PriorityBlockingQueue<?>) {
        // 如果指定集是一个优先级阻塞队列，则将其比较器作为优先级阻塞队列的比较器。
        PriorityBlockingQueue<? extends E> pq = (PriorityBlockingQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        screen = false;
        // exact match
        // 精确匹配（instanceof只能判断传入的指定集是优先级阻塞队列的子类（包含本身），而只有通过类型的具体判断才能判断是否真的是优
        // 先级阻塞队列。如果指定集是优先级阻塞队列的子类，则单纯获取到比较器是无法判断具体的排序的，因为谁也不知道子类的实现是怎样，
        // 因此只有判断指定集就是优先级阻塞队列才能确定这一点）。
        if (pq.getClass() == PriorityBlockingQueue.class)
            heapify = false;
    }
    // 获取指定集的元素数组拷贝。
    Object[] a = c.toArray();
    int n = a.length;
    // 如果指定集的类型不是数组列表，则返回的元素数组拷贝可能因为协变的原因不是Object，因此需要再进行一次拷贝确保没有问题。
    if (c.getClass() != ArrayList.class)
        a = Arrays.copyOf(a, n, Object[].class);
    // 如果需要筛选null，并且元素总数为1或者比较为不为null，则直接进行null的扫描。screen为true，说明指定集中可能包含null元素，需要
    // 进行筛选。如果指定集中只有一个元素，则该元素很有可能因为无需进行比较而遗漏了空检查，从而使的一个null元素加入了优先级阻塞队列。
    // 如果比较器不为null，则由于比较其本身是可能允许null元素的比较的，因此也需要进行筛选。
    if (screen && (n == 1 || this.comparator != null)) {
        // 判断是否有元素为null。
        for (int i = 0; i < n; ++i)
            if (a[i] == null)
                throw new NullPointerException();
    }
    // 将赋值元素数组和大小。
    this.queue = a;
    this.size = n;
    // 将数据进行堆化，本质就是进行排序。该操作是针对那些没有强制性排序需求的集的。
    if (heapify)
        heapify();
}

三 方法

---

 插入

• public boolean add(E e) —— 新增 —— 向当前优先级阻塞队列的尾部插入指定元素，并根据比较器/能力将之排序到合适位置。该方法是尾部插入方法“异常”形式的实现，当当前优先级阻塞队列存在剩余容量时插入并返回true；否则抛出非法状态异常。虽说定义如此，但实际由于优先级阻塞队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会抛出非法状态异常，而只会在堆内存不足时抛出内存溢出错误。由于优先级阻塞队列类基于数组实现，因此最大容量实际还受限于Integer.MAX_VALUE。当元素总数触达该上限时，为了掩盖实际实现上的限制，会手动抛出内存溢出错误。

• public boolean offer(E e) —— 提供 —— 向当前优先级阻塞队列的尾部插入指定元素，并根据比较器/能力将之排序到合适位置。该方法是尾部插入方法“特殊值”形式的实现，当当前优先级阻塞队列存在剩余容量时插入并返回true；否则返回false。虽说定义如此，但实际由于优先级阻塞队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会抛出非法状态异常，而只会在堆内存不足时抛出内存溢出错误。由于优先级阻塞队列类基于数组实现，因此最大容量实际还受限于Integer.MAX_VALUE。当元素总数触达该上限时，为了掩盖实际实现上的限制，会手动抛出内存溢出错误。

• public void put(E e) —— 放置 —— 向当前优先级阻塞队列的尾部插入指定元素，并根据比较器/能力将之排序到合适位置。该方法是尾部插入方法“阻塞”形式的实现，当当前优先级阻塞队列存在剩余容量时插入；否则等待至存在剩余容量为止。虽说定义如此，但实际由于优先级阻塞队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会抛出非法状态异常，而只会在堆内存不足时抛出内存溢出错误。由于优先级阻塞队列类基于数组实现，因此最大容量实际还受限于Integer.MAX_VALUE。当元素总数触达该上限时，为了掩盖实际实现上的限制，会手动抛出内存溢出错误。

• public boolean offer(E e, long timeout, TimeUnit unit) —— 提供 —— 向当前优先级阻塞队列的尾部插入指定元素，并根据比较器/能力将之排序到合适位置。该方法是尾部插入方法“超时”形式的实现，当当前优先级阻塞队列存在剩余容量时插入并返回true；否则在指定等待时间内等待至存在剩余容量为止，超出指定等待时间则返回false。虽说定义如此，但实际由于优先级阻塞队列类是真正的无界队列，最大容量只受限于堆内存的大小，故而永远不会抛出非法状态异常，而只会在堆内存不足时抛出内存溢出错误。由于优先级阻塞队列类基于数组实现，因此最大容量实际还受限于Integer.MAX_VALUE。当元素总数触达该上限时，为了掩盖实际实现上的限制，会手动抛出内存溢出错误。

 移除

• public E remove() —— 移除 —— 从当前优先级阻塞队列的头部移除并获取排序最靠前的元素，并触发后续元素的重排序。该方法是头部移除方法“异常”形式的实现，当当前优先级阻塞队列存在元素时移除并返回头元素；否则抛出无元素异常。
      优先级阻塞队列类并没有自实现remove()方法，而是直接使用了父类AbstractQueue（抽象队列）抽象类的实现。在实现中其调用了头部移除方法“特殊值”形式的poll()方法来达成目的，使得所有抽象队列抽象类的子类只需实现poll()方法后就可以正常调用remove()方法。这种代码结构是设计模式的一种，被称为“模板模式”。

/**
 * Retrieves and removes the head of this queue.  This method differs from {@link #poll poll} only in that it throws an exception if this queue is empty.
 * 检索并移除队列的头。该方法不同于poll()方法，如果队列为空时其会抛出一个异常。
 * <p>
 * This implementation returns the result of <tt>poll</tt> unless the queue is empty.
 * 除非队列为空，否则该实现返回poll()的结果。
 *
 * @return the head of this queue 队列的头（元素）
 * @throws NoSuchElementException if this queue is empty
 *                                无元素异常：如果队列为空
 */
public E remove() {
    // 调用poll()方法获取元素。
    E x = poll();
    if (x != null)
        // 如果元素存在，直接返回。
        return x;
    else
        // 如果元素不存在，抛出无元素异常。
        throw new NoSuchElementException();
}

• public E poll() —— 轮询 —— 从当前优先级阻塞队列的头部移除并获取排序最靠前的元素，并触发后续元素的重排序。该方法是头部移除方法“特殊值”形式的实现，当当前优先级阻塞队列存在元素时移除并返回头元素；否则返回null。

• public E take() throws InterruptedException —— 拿取 —— 从当前优先级阻塞队列的头部移除并获取排序最靠前的元素，并触发后续元素的重排序。该方法是头部移除方法“阻塞”形式的实现，当当前优先级阻塞队列存在元素时移除并返回头元素；否则等待至存在元素为止。

• public E poll(long timeout, TimeUnit unit) throws InterruptedException —— 轮询 —— 从当前优先级阻塞队列的头部移除并获取排序最靠前的元素，并触发后续元素的重排序。该方法是头部移除方法“超时”形式的实现，当当前优先级阻塞队列存在元素时移除并返回头元素；否则在指定等待时间内等待至存在元素为止，超出指定等待时间则返回null。

• public boolean remove(Object o) —— 移除 —— 从当前优先级阻塞队列中按迭代器顺序移除首个指定元素，成功则返回true；否则返回false。
      由于指定元素可能处于任意位置（不一定是头/尾），因此被称为内部移除。内部移除并不是常用的方法：一是其不符合FIFO的数据操作方式；二是各类实现为了提高性能可能会使用各种优化策略，而remove(Object o)方法往往无法适配这些策略，导致性能较/极差。

• public void clear() —— 清理 —— 从当前优先级阻塞队列中移除所有元素。

 检查

• public E element() —— 元素 —— 从当前优先级阻塞队列的头部获取排序最靠前的元素。该方法是头部检查方法“异常”形式的实现，当当前优先级阻塞队列存在元素时返回头元素；否则抛出无元素异常。
      与remove()方法相同，优先级阻塞队列类并没有自实现element()方法，而是直接使用了父类AbstractQueue（抽象队列）抽象类的实现（具体源码如下）。在实现中其调用了检查方法“特殊值”形式的peek()方法来达成目的，使得所有抽象队列抽象类的子类只需实现peek()方法后就可以正常调用element()方法。这种代码结构是设计模式的一种，被称为“模板模式”。

/**
 * Retrieves, but does not remove, the head of this queue. This method differs from {@link #peek peek} only in that it throws an exception if this
 * queue is empty.
 * 检索，但不移除队列的头（元素）。该方法不同于peek()方法，如果队列为空时其会抛出一个异常。
 * <p>
 * This implementation returns the result of <tt>peek</tt> unless the queue is empty.
 * 除非队列为空，否则该实现返回peek()的结果。
 *
 * @return the head of this queue 队列的头（元素）
 * @throws NoSuchElementException if this queue is empty
 *                                无元素异常：如果队列为空
 * @Description: 元素：用于返回队列的头元素（但不移除）。当队列中不存在元素时抛出无元素异常。
 */
public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

• public E peek() —— 窥视 —— 从当前优先级阻塞队列的头部获取排序最靠前的元素。该方法是头部检查方法“特殊值”形式的实现，当当前优先级阻塞队列存在元素时返回头元素；否则返回null。

 流失

• public int drainTo(Collection<? super E> c) —— 流失 —— 将当前优先级阻塞队列中的所有元素流失到指定集中，并返回流失的元素总数。被流失的元素将不再存在于当前优先级阻塞队列中。

• public int drainTo(Collection<? super E> c, int maxElements) —— 流失 —— 将当前优先级阻塞队列中最多指定数量的元素流失到指定集中，并返回流失的元素总数。被流失的元素不再存在于当前优先级阻塞队列中。

 查询

• public int size() —— 大小 —— 获取当前优先级阻塞队列的元素总数。

• boolean isEmpty() —— 是否为空 —— 判断当前优先级阻塞队列是否为空，是则返回true；否则返回false。

• public int remainingCapacity() —— 剩余容量 —— 获取当前优先级阻塞队列的剩余容量。由于优先级阻塞队列类是无界队列，因此该方法永远返回Integer.MAX_VALUE。

• public Object[] toArray() —— 转化数组 —— 获取按迭代器顺序包含当前优先级阻塞队列中所有元素的新数组。

• public <T> T[] toArray(T[] a) —— 转化数组 —— 获取按迭代器顺序包含当前优先级阻塞队列中所有元素的泛型数组。如果参数泛型数组长度足以容纳所有元素，则令之承载所有元素后返回。并且如果参数泛型数组的长度大于当前优先级阻塞队列的元素总数，则将已承载所有元素的参数泛型数组的size索引位置设置为null，表示从当前优先级阻塞队列中承载的元素到此为止。当然，该方案只对不允许保存null元素的集有效。如果参数泛型数组的长度不足以承载所有元素，则重分配一个相同泛型且长度与当前优先级阻塞队列元素总数相同的新泛型数组以承载所有元素后返回。

 迭代器

• public Iterator iterator() —— 迭代器 —— 创建可遍历当前优先级阻塞队列中元素的迭代器。

    事实上，上文中只列举了大部分常用方法。由于优先级阻塞队列类是集接口的实现类，因此其也实现了其定义的所有方法，例如contains(Object o)、removeAll(Collection<?> c)、containsAll(Collection<?> c)等。但由于这些方法的执行效率不高，并且与优先级阻塞队列类的主流使用方式并不兼容/兼容性差，因此通常是不推荐使用的，有兴趣的童鞋可以去查看源码实现。

四 排序

---

 上排序

    上排序是顶堆的两种排序方式之一，本质是通过上移将指定元素排序到元素数组的合适位置。上排序的主要流程是将指定元素与其父元素进行对比，如果指定元素小于父元素（小顶堆规则），则将指定元素与父元素的位置进行交换，随后重复这个过程，直至指定元素等于/大于父元素或指定元素成为根元素为止。具体如下图所示：

    在优先级阻塞队列类中，上排序主要发生于插入方法，次要发生于内部移除方法。根据调用方法的不同，上排序的起点也会有所差异。对于插入方法，会如上图所示般将新元素插入于优先级阻塞队列/元素数组的尾部后完成整个上排序操作；而对于内部移除方法，由于移除的指定元素可能是优先级阻塞队列/元素数组的中间元素，因此上排序的起点可能位于优先级阻塞队列/元素数组的中间位置，即被移除指定元素所在的位置。
    需要注意的是：由于在内部移除方法中上排序起点位置的指定元素已被移除，因此需要将优先级阻塞队列/元素数组的尾元素迁移至起点位置作为排序的指定元素，而选择尾元素的原因是为了避免小顶堆/完全二叉树的“完全”性质被破坏。此外内部移除方法未必一定会执行上排序，执行上排序的前提是下排序的失败，即指定元素经过下排序后还处于原来的位置。

 下排序

    上排序是顶堆的两种排序方式之一，本质是通过下移将指定元素排序到元素数组的合适位置。下排序的主要流程是将指定元素与其左/右子元素进行对比，如果指定元素大于左/右子元素的任意一个（小顶堆规则），则将指定元素与左/右子元素中较小的一个的位置进行交换，随后重复这个过程，直至指定元素小于/等于左/右子元素或指定元素成为叶子元素为止。具体如下图所示：

    在优先级阻塞队列中，上排序主要发生于头部移除方法，次要发生于内部移除方法。根据调用方法的不同，下排序的起点也会有所差异。对于头部移除方法，由于头元素已被移除，故而会将尾元素迁移至队头并完成整个下排序操作；而对于内部移除方法，与头部移除操作同理，由于指定元素已被移除，因此同样会将尾元素移动至指定元素所在的位置。并且因为移除的指定元素可能是优先级阻塞队列/元素数组的中间元素，所以下排序的起点可能位于优先级阻塞队列/元素数组的中间位置。

    需要注意的是：在内部移除方法中下排序可能没有效果，即起点位置的元素经过下排序后还处于原来的位置。原因可能是因为元素小于/等于左/右子元素或元素已是叶子元素。在这种情况下需要继续进行上排序，确保元素在优先级阻塞队列/元素数组中处于合适的位置。

 堆化

    所谓堆化，本质是批量的下排序，是仅在PriorityBlockingQueue(Collection<? extends E> c)构造方法中才会发生的特殊排序行为。由于指定集中的元素未必会按比较器/能力的顺序进行排序，由此需要针对整个元素数组而非某单个元素进行下排序。堆化的具体流程是针对优先级阻塞队列/元素数组中的前半段元素进行由后向前的批量下排序。如果是由前向后，由于后方元素乱序的原因，可能会导致最终结果存在父元素大于子元素的情况，由于后半段元素是前半段的子元素，因此会在过程中也完成排序。具体如下图所示：

五 扩容/线程安全机制的特殊处理

---

    优先级阻塞队列的扩容机制并不复杂，在上文中基本已经全部讲清，此处会再小幅度的补充部分细节。

    关于扩容，具体可以划分为分配新元素数组、设置新元素数组及元素迁移三个阶段。其中设置新元素数组与元素迁移并无补充内容可言，但关于分配新元素数组阶段则还存在一个值得一说的知识点，即线程安全机制的特殊处理。

    一般情况下，优先级阻塞队列会通过单个可重入锁来保证线程安全。而一旦在插入方法中触发扩容，则会解开悲观锁加乐观锁（避免多个线程分配新元素数组）来分配新元素数组。解开悲观锁的原因是因为分配新元素数组的过程无需操作旧元素数组，故而优先级阻塞队列类完全可以支持分配新元素数组与公共方法执行的并发。而加乐观锁的原因则是因为在分配新元素数组期间，由于悲观锁解开的原因可能会有新插入者触发扩容导致重复的数组分配，而通过乐观锁则可以避免绝大多数重复分配的情况。虽然由于新元素数组分配完成后解开乐观锁和重新加上悲观锁之间存在空隙导致该情况无法完全避免，但这种场景是极为少见的，并且也可以通过后续的判断来避免错误。

    当重新加上悲观锁后方法会执行设置新元素数组和元素迁移两个阶段。执行前其会先判断元素数组是否已被替换，是则说明有线程先完成了扩容，当前线程的扩容已没有意义，直接略过；否则设置新元素数组并进行元素迁移。设置新元素数组只是简单的赋值操作，而元素迁移则是通过拷贝完成的。