Java中的Java.util.PriorityQueue类|极客笔记

Java中的Java.util.PriorityQueue类

PriorityQueue是Java.util包中的一个类，它以优先级队列方式存储数据。在PriorityQueue中，每个元素都有一个优先级，元素会按优先级被先后出队列。优先级队列具有以下特性：

元素必须可比较；
底层存储采用堆排序；
每次出队的是优先级最高的元素；
出队操作后，优先级队列会重新进行堆排序；

PriorityQueue类的API定义如下：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    // Constructors
    PriorityQueue();
    PriorityQueue(int initialCapacity);
    PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
    PriorityQueue(Comparator<? super E> comparator)
    PriorityQueue(Collection<? extends E> c);

    // Operations
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
    // ...
}

我们可以通过以下方式构建一个PriorityQueue对象，并向其中加入元素：

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(5);
queue.offer(2);
queue.offer(8);
queue.offer(1);
queue.offer(6);

System.out.println(queue);

以上代码会输出如下结果：

[1, 2, 8, 5, 6]

可以看到，PriorityQueue自动按照元素的大小进行排序。我们也可以使用匿名内部类或Lambda表达式自定义元素比较方式：

PriorityQueue<Integer> queue = new PriorityQueue<>(10, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        // 自定义比较方式
        return o2 - o1;
    }
});

queue.offer(5);
queue.offer(2);
queue.offer(8);
queue.offer(1);
queue.offer(6);

System.out.println(queue);

输出结果如下：

[8, 6, 5, 2, 1]

注意，在使用自定义比较器时，我们必须指定队列初始容量。

Java7中的PriorityQueue小坑

在Java7中，PriorityQueue的实现使用数组存储，并且数组顺序不一定和 PriorityQueue 中的元素顺序完全一致。原因是，当需要进行有序存储的时候，数组的大小并不一定会动态增长，而是等到size array.length时，才一次性扩容至2倍。

这里简单演示这个问题：

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(2);
queue.offer(5);
queue.offer(8);
queue.offer(1);
queue.offer(6);

// 本意是想按逆序出队，但是结果并不如你所愿
for (int i = queue.size(); i > 0; i--) {
    System.out.print(queue.poll() + " ");
}

输出结果是：

1 2 8 5 61

为了避免数组存储造成的影响，我们建议构造PriorityQueue时设置它的初始容量：

PriorityQueue<Integer> queue = new PriorityQueue<>(10, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        // 自定义比较方式
        return o2 - o1;
    }
});

queue.offer(2);
queue.offer(5);
queue.offer(8);
queue.offer(1);
queue.offer(6);

for (int i = queue.size(); i > 0; i--) {
    System.out.print(queue.poll() + " ");
}

上述代码的输出结果正确地为：