Java PriorityQueue指南

1. 概述

在这个简短的教程中，我们将探讨Java实现的优先队列。首先，我们会介绍标准用法，并通过自然顺序和逆序对队列进行排序展示一些例子。

最后，我们将看到如何使用Java的Comparator自定义排序。

2. java.util.PriorityQueue

java.util.PriorityQueue类从JDK 1.5版本开始提供，它还包含其他*AbstractQueue的实现。如其名称所示，我们使用PriorityQueue在给定的集合中维护一个定义好的排序：队列的头部（head）是根据我们指定的排序，是最小的元素。每次从队列中取出操作（poll、remove或peek）都会读取队列的头部。

内部地，PriorityQueue依赖于一个对象数组。如果初始指定的容量（默认为JDK 17中的11）不足以存储所有项目，这个数组会自动扩容。虽然向PriorityQueue提供初始容量不是强制性的，但如果已知集合的大小，我们可以避免不必要的自动扩容，从而节省CPU周期。

在Javadoc中，说明了这个实现对于添加和移除方法（offer、poll、remove和add）的时间复杂度为O(log(n))。这得益于每个对队列进行编辑时，都维护了一个平衡二叉堆数据结构。而remove(Object)和contains(Object)方法的时间复杂度为线性，检索方法（peek、element和size）的时间复杂度为常数。

3. 自然顺序和逆序

在之前的文章中，我们介绍了如何根据元素的自然顺序将它们插入到PriorityQueue中。这是因为初始化一个没有指定Comparator的优先队列，会直接使用compare操作来排序元素。

例如，现在让我们看看，通过提供标准的Integer自然排序比较器或null，队列将以相同的方式排序：

PriorityQueue<Integer> integerQueue = new PriorityQueue<>();
PriorityQueue<Integer> integerQueueWithComparator = new PriorityQueue<>((Integer c1, Integer c2) -> Integer.compare(c1, c2));

integerQueueWithComparator.add(3);
integerQueue.add(3);

integerQueueWithComparator.add(2);
integerQueue.add(2);

integerQueueWithComparator.add(1);
integerQueue.add(1);

assertThat(integerQueue.poll())
     .isEqualTo(1)
     .isEqualTo(integerQueueWithComparator.poll());

assertThat(integerQueue.poll())
     .isEqualTo(2)
     .isEqualTo(integerQueueWithComparator.poll());

assertThat(integerQueue.poll())
     .isEqualTo(3)
     .isEqualTo(integerQueueWithComparator.poll());

现在，让我们创建一个按逆自然顺序排序的PriorityQueue。我们可以通过使用java.util.Collections.reverseOrder()静态方法来实现：

PriorityQueue<Integer> reversedQueue = new PriorityQueue<>(Collections.reverseOrder());

reversedQueue.add(1);
reversedQueue.add(2);
reversedQueue.add(3);

assertThat(reversedQueue.poll()).isEqualTo(3);
assertThat(reversedQueue.poll()).isEqualTo(2);
assertThat(reversedQueue.poll()).isEqualTo(1);

4. 定制排序

现在让我们尝试为自定义类定义一种特殊的排序方式。首先，类需要实现Comparable接口，或者在创建队列时提供一个Comparator，否则会抛出ClassCastException。

例如，我们创建一个ColoredNumber类来演示这种行为：

public class ColoredNumber {

   private int value;
   private String color;

   public ColoredNumber(int value, String color) {
       this.value = value;
       this.color = color;
   }

当我们尝试将这个类用于PriorityQueue时，会抛出异常：

PriorityQueue<ColoredNumber> queue = new PriorityQueue<>();
queue.add(new ColoredNumber(3,"red"));
queue.add(new ColoredNumber(2, "blue"));

这是因为PriorityQueue不知道如何通过与其他同类型对象的比较来对ColoredNumber对象进行排序。

我们可以通过在构造函数中提供Comparator来提供排序，就像前面的例子一样，或者实现Comparable接口：

public final class ColoredNumberComparable implements Comparable<ColoredNumber> {
// ...
@Override
public int compareTo(ColoredNumberComparable o) {
   if ((this.color.equals("red") && o.color.equals("red")) ||
           (!this.color.equals("red") && !o.color.equals("red"))) {
       return Integer.compare(this.value, o.value);
   }
   else if (this.color.equals("red")) {
       return -1;
   }
   else {
       return 1;
   }
}

这样，每个项目将按照“红色”颜色首先排序，然后是自然顺序的值，这意味着所有红色对象将首先返回：

PriorityQueue<ColoredNumberComparable> queue = new PriorityQueue<>();
queue.add(new ColoredNumberComparable(10, "red"));
queue.add(new ColoredNumberComparable(20, "red"));
queue.add(new ColoredNumberComparable(1, "blue"));
queue.add(new ColoredNumberComparable(2, "blue"));

ColoredNumberComparable first = queue.poll();
assertThat(first.getColor()).isEqualTo("red");
assertThat(first.getValue()).isEqualTo(10);

queue.poll();

ColoredNumberComparable third = queue.poll();
assertThat(third.getColor()).isEqualTo("blue");
assertThat(third.getValue()).isEqualTo(1);

关于多线程的一点注意事项：Java的PriorityQueue实现是非同步的，这意味着多个线程不应并发使用同一个PriorityQueue实例。

如果需要多个线程访问PriorityQueue实例，应使用线程安全的java.util.concurrent.PriorityBlockingQueue类。

5. 总结

在这篇文章中，我们了解了Java PriorityQueue的实现工作原理。我们从类的JDK内部结构及其读写元素的性能开始，然后展示了具有自然排序和逆序的PriorityQueue。最后，我们为用户自定义类提供了一个可比较的实现，并验证了其排序行为。

如往常一样，代码可以在GitHub上找到。