Java优先队列：深入理解与高效应用

2 年 ago
文, 翔
2 minutes

在某些场景下，我们需要按照特定顺序处理队列中的项目。优先队列（PriorityQueue）作为一种特殊的数据结构，能够有效地实现这一需求。与传统的“先进先出”（FIFO）队列不同，Java 中的优先队列是根据项目的优先级来检索元素的。

Java 优先队列详解

Java PriorityQueue 类图

Java 优先队列的构造函数

Java 优先队列提供了多种构造函数选项，以满足不同的初始化需求：

  1. PriorityQueue()：创建一个具有默认初始容量（即 11）的优先队列。
  2. PriorityQueue(Collection<? extends E> c)：创建一个包含指定集合中所有元素的优先队列。
  3. PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的优先队列。
  4. PriorityQueue(int initialCapacity, Comparator<? super E> comparator)：创建一个具有指定初始容量，并根据提供的比较器对其元素进行排序的优先队列。
  5. PriorityQueue(PriorityQueue<? extends E> c)：创建一个包含指定优先队列中所有元素的优先队列。
  6. PriorityQueue(SortedSet<? extends E> c)：创建一个包含指定排序集合中所有元素的优先队列。

除非在创建时提供了比较器，否则优先队列的元素将按照其自然顺序进行排序。默认情况下，元素按升序排列，因此队列的头部（即通过 peek() 或 poll() 方法获取的元素）是优先级最低的元素。如果存在两个或多个元素同时具备成为头元素的资格，系统将任意选择其中一个。

Java 优先队列示例

让我们通过一个示例来创建一个包含各种任务的优先队列：

PriorityQueue<String> tasks = new PriorityQueue<>();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

上述代码将创建一个任务的优先队列，其中的任务将按照字符串的自然顺序进行排序。现在，让我们再创建一个按照自然顺序的相反顺序排序任务的优先队列。为此，我们需要传递一个比较器：

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

Java 优先队列的常用方法

接下来，我们将详细介绍 PriorityQueue 类提供的一些常用方法及其用法：

  1. boolean add(E e)：将指定的元素插入到队列中。我们已经在上面的示例中使用此方法添加了 5 个任务。
  2. Comparator<? super E> 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. E poll()：此方法也检索队列的头部（具有最高优先级的元素），如果队列为空则返回 null。但与 peek() 不同的是，它还会从队列中移除该元素。例如，如果我们先调用 poll()： 
    System.out.println("在 tasks 上进行 Poll：" + tasks.poll());
System.out.println("在 reverseTasks 上进行 Poll：" + reverseTasks.poll());

    然后再次调用 peek()：

    System.out.println("在 tasks 上进行 Peek：" + tasks.peek());
System.out.println("在 reverseTasks 上进行 Peek：" + reverseTasks.peek());

    我们将得到以下输出：

    在 tasks 上进行 Poll：task1
在 reverseTasks 上进行 Poll：task5
在 tasks 上进行 Peek：task2
在 reverseTasks 上进行 Peek：task4
  7. int size()：返回队列中的元素数量。
  8. boolean remove(Object o)：从队列中删除指定的元素（如果存在）。如果存在两个相同的元素，它只会删除其中一个。
  9. Object[] toArray()：返回一个包含队列中所有元素的数组。
  10. <T> T[] toArray(T[] a)：返回一个包含队列中所有元素的数组，返回数组的类型与指定数组的类型相同。
  11. Iterator<E> iterator()：返回队列的迭代器。
  12. void clear()：从队列中移除所有元素。

此外，优先队列还继承了 Collection 和 Object 类的方法。

Java 优先队列的时间复杂度

了解优先队列操作的时间复杂度对于性能优化至关重要：

  1. 对于入队（add(), offer()）和出队（poll()）方法，时间复杂度为 O(log(n))。
  2. 对于 remove(Object) 和 contains(Object) 方法，时间复杂度为 O(n)（线性时间）。
  3. 对于检索方法（如 peek()），时间复杂度为 O(1)（常数时间）。

需要注意的是，PriorityQueue 的当前实现不是线程安全的。因此，如果需要在多线程环境下进行同步访问，应使用 PriorityBlockingQueue。更多详细信息，请参考 Java API 文档。

bannerAds