【Java数据结构及算法实战】系列011：数组实现的优先级队列PriorityQueue

PriorityQueue是基于数组实现的无界优先级队列。PriorityQueue中的元素按其自然顺序排序，或由队列构造时提供的比较器根据所使用的构造函数排序。优先级队列不允许空元素，依赖自然顺序的优先级队列也不允许插入不可比较的对象。

PriorityQueue本质上就是一个最小堆存储结构数组，通过“极大优先级堆”实现的，即堆顶元素是优先级最大的元素。堆的操作，主要就是两个：siftUp（向上调整堆）和siftDown（向下调整堆）。

PriorityQueue的队首是相对于指定顺序来说优先级的值最小的元素。如果多个元素优先级的值都是最小，那么头部就是其中一个元素。PriorityQueue的检索操作poll、remove和peek等都是访问位于队首的元素。

PriorityQueue是无界队列，因此插入的元素是无限制的，但其具有一个内部容量，它控制用于在队列上存储元素的数组的大小。它总是至少和队列一样大。当元素被添加到优先级队列时，其容量会自动增长。

PriorityQueue及其迭代器实现了Collection和Iterator接口的所有可选方法。方法itilerator()提供的迭代器和方法spliterator()提供的分离器并不保证以任何特定的顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用Arrays.sort(pq.toArray()).。

注意PriorityQueue是唯一一个非线程安全的队列实现类，适合用于单线程存放数据并且将数据排序。如果是在多个线程中有修改了队列的场景，那么不应该用线程PriorityQueue，而应该使用线程安全的java.util.concurrent.PriorityBlockingQueue类。

PriorityQueue是Java Collections Framework的一个成员。

1.   PriorityQueue的声明

PriorityQueue的接口和继承关系如下

public class PriorityQueue extends AbstractQueue

    implements java.io.Serializable {

   …

}

完整的接口继承关系如下图所示。

从上述代码可以看出，PriorityQueue既实现了java.io.Serializable接口，又继承了java.util.AbstractQueue。

2.   PriorityQueue的成员变量和构造函数

以下是PriorityQueue的构造函数和成员变量。

// 默认数组容量

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

   

// 元素数组

    transient Object[] queue;

   

// 队列中的元素个数

    int size;

    // 比较器

    private final Comparator