Java 优先队列

教程
Java

不时地，我们需要按特定顺序处理队列中的项目。优先队列是完成此任务的一种数据结构。Java优先队列与“正常”的队列不同。它不是“先进先出”，而是按照项目的优先级检索它们。

Java优先队列

java.util.PriorityQueue类通过在内部使用优先堆实现，为我们提供了这种数据类型的实现。Java优先队列是无界队列。它在Java 1.5中引入，并在Java SE 8版本中进行了增强。优先队列在内部通过遵循“优先堆”数据结构来实现。这是PriorityQueue类层次结构： 优先队列类图：

Java优先队列构造函数

  1. PriorityQueue() – 使用默认初始容量（即11）创建优先队列
  2. PriorityQueue(Collection c) – 使用指定集合中的元素创建优先队列
  3. PriorityQueue(int initialCapacity) – 使用指定的初始容量创建一个PriorityQueue
  4. PriorityQueue(int initialCapacity, Comparator comparator) – 使用提供的初始容量创建一个PriorityQueue，并根据指定的比较器对其元素进行排序
  5. PriorityQueue(PriorityQueue c) – 创建一个包含指定优先级队列中元素的PriorityQueue
  6. 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，它按照自然顺序的相反顺序排序任务。因此，我们需要传递一个比较器：

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue 方法

现在，让我们看一下 PriorityQueue 可用的所有方法并使用它们：

  1. Boolean add(E e) – 此方法将指定的元素插入队列中。我们已经使用此方法将 5 个任务添加到我们的队列中。

  2. Comparator comparator() – 此方法返回用于按照顺序排列此队列中的元素的 Comparator。如果未指定比较器并且队列根据其元素的自然顺序进行排序，则返回 null。因此，如果我们执行以下操作：

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    输出将是：

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – 如果队列包含指定的元素，则返回true。让我们检查“task3”是否属于优先级队列tasks：

    System.out.println(tasks.contains("task3"));

    这将打印：

    true

  4. boolean offer(E e) – 类似于add()方法，该方法还将元素添加到队列中。对于容量受限的队列，offer()方法和add()方法实际上略有不同，但在PriorityQueue的情况下，两者相同。与add()不同，即使在无法将元素添加到队列中时，offer()也不会抛出异常。

  5. E peek() – 检索此队列的头部，如果此队列为空，则返回null。换句话说，它返回具有最高优先级的元素。所以下面的代码：

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    给我们：

    task1
task5

  6. epoll() – 这个方法也会检索队列头部（具有最高优先级的元素），如果队列为空则返回 null。但与 peek() 不同的是，它还会移除元素。因此，如果我们调用 poll()：

    System.out.println(“对 tasks 进行轮询：”+tasks.poll());
System.out.println(“对 reverseTasks 进行轮询：”+reverseTasks.poll());

    然后再 peek：

    System.out.println(“对 tasks 进行查看：”+tasks.peek());
System.out.println(“对 reverseTasks 进行查看：”+reverseTasks.peek());

    我们将会得到以下输出：

    对 tasks 进行轮询：task1
对 reverseTasks 进行轮询：task5
对 tasks 进行查看：task2
对 reverseTasks 进行查看：task4

  7. int size() – 返回队列中的元素数。

  8. boolean remove(Object o) – 从队列中移除指定的元素（如果存在）。如果存在两个相同的元素，则仅移除其中一个。

  9. Object[] toArray() – 返回包含队列中所有元素的数组。

  10. T[] toArray(T[] a) – 返回一个包含队列中所有元素的数组，返回的数组类型与指定数组的类型相同。

  11. Iterator iterator() – 返回队列的迭代器。

  12. void clear() – 从队列中移除所有元素。

除此之外，PriorityQueue 还继承了 Collection 和 Object 类的方法。

Java PriorityQueue 时间复杂度

  1. 对于入队和出队方法，时间复杂度为 O(log(n))
  2. 对于 remove(Object) 和 contains(Object) 方法，时间复杂度为线性
  3. 对于检索方法，时间复杂度为常数

这个优先队列的实现不是线程安全的。所以，如果我们需要同步访问，我们需要使用 PriorityBlockingQueue。参考：API 文档

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java