优先级队列 Java
我们时不时需要按特定顺序处理队列中的项目。优先级队列是一种可以完成此任务的数据结构。Java 优先级队列不同于“普通”队列。它不是按“先进先出”的顺序，而是按优先级顺序检索项目。
优先级队列 Java
该类java.util.PriorityQueue通过在内部使用优先级堆实现为我们提供了这种数据类型的实现。Java PriorityQueue 是一个无界队列。它是在 Java 1.5 中引入的，并在 Java SE 8 版本中得到增强。PriorityQueue 在内部通过以下“优先级堆”数据结构实现。以下是 PriorityQueue 类层次结构：
PriorityQueue 类图：
Java PriorityQueue 构造函数
- PriorityQueue() - 创建一个具有默认初始容量的 PriorityQueue，即 11
- PriorityQueue(Collection c) - 使用指定集合中的元素创建一个 PriorityQueue
- PriorityQueue(int initialCapacity) - 创建具有指定初始容量的 PriorityQueue
- PriorityQueue(int initialCapacity, Comparator comparator) - 创建一个具有提供的初始容量的 PriorityQueue，其元素的排序根据指定的比较器
- PriorityQueue(PriorityQueue c) - 创建一个包含指定优先级队列中的元素的 PriorityQueue
- PriorityQueue(SortedSet c) - 创建一个包含指定排序集合中的元素的 PriorityQueue
优先级队列元素按其自然顺序排列，除非我们Comparator在创建时提供。默认情况下，元素按升序排列，因此队列的头部是优先级最低的元素。如果有两个元素同时有资格成为头部，则这种关系将被任意打破。
Java PriorityQueue 示例
让我们创建一个PriorityQueue包含各种任务的：
PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");
这将创建一个 PriorityQueue 任务，它将按照 的自然顺序进行排序String。让我们创建另一个 PriorityQueue，它按与自然顺序相反的顺序对任务进行排序。因此我们需要传递一个 Comparator：
PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");
Java PriorityQueue 方法
现在，让我们看一下 PriorityQueue 可用的所有方法并使用它们：
-
Boolean add(E e) - 此方法将指定元素插入队列。我们已经使用此方法在队列中添加了 5 个任务。
-
Comparator comparator() - 此方法返回用于排序此队列中元素的 Comparator。如果未指定比较器，则返回 null，并且队列根据其元素的自然顺序进行排序。因此，如果我们这样做：
System.out.println(tasks.comparator()); System.out.println(reverseTasks.comparator());输出将是：
null java.util.Collections$ReverseComparator@15db9742 -
boolean contains(Object o) - 如果队列包含指定元素，则返回 true。让我们检查“task3”是否属于优先级队列任务：
System.out.println(tasks.contains("task3"));这将打印：
true -
boolean offer(E e) - 与 add() 方法一样，此方法也会向队列添加元素。对于容量受限的队列，offer() 和 add() 方法实际上略有不同，但对于 PriorityQueue，两者相同。与 add() 不同，即使无法将元素添加到队列中，offer() 也不会引发异常。
-
E peek() - 检索此队列的头部，如果此队列为空，则返回 null。换句话说，它返回优先级最高的元素。因此以下代码：
System.out.println(tasks.peek()); System.out.println(reverseTasks.peek());给我们：
task1 task5 -
E poll() - 此方法还会检索队列的头部（优先级最高的元素），如果队列为空，则返回 null。但与 peek() 不同，它还会删除元素。因此，如果我们调用 poll()：
System.out.println(“Poll on tasks: ”+tasks.poll()); System.out.println(“Poll on reverseTasks: ”+reverseTasks.poll());然后看一下：
System.out.println(“Peek on tasks: ”+tasks.peek()); System.out.println(“Peek on reverseTasks: ”+reverseTasks.peek());我们将得到以下输出：
Poll on tasks: task1 Poll on reverseTasks: task5 Peek on tasks: task2 Peek on reverseTasks: task4 -
int size() - 返回队列中的元素数量。
-
boolean remove(Object o) - 如果存在，则从队列中删除指定元素。如果存在两个相同的元素，则只删除其中一个。
-
Object[] toArray() - 返回包含队列中所有元素的数组。
-
T[] toArray(T[] a) - 返回包含队列中所有元素的数组，返回数组的类型为指定数组的类型。
-
迭代器 iterator() - 返回队列的迭代器。
-
void clear() - 从队列中删除所有元素。
除此之外，还继承了和类PriorityQueue的方法。CollectionObject
Java PriorityQueue 时间复杂度
- 对于入队和出队方法，时间复杂度为 O(log(n))
- 对于 remove(Object) 和 contains(Object) 方法，时间复杂度是线性的
- 对于检索方法，它具有恒定的时间复杂度
此优先级队列实现不是线程安全的。因此，如果我们需要同步访问，则需要使用PriorityBlockingQueue。参考：API 文档