Java中的PriorityQueue

Java中的PriorityQueue是一种优先队列。它是一个内部使用堆数据结构来实现的基于优先级的队列。优先级队列中的元素被赋予优先级，而PriorityQueue则根据元素的优先级进行排序。当你从PriorityQueue中添加或移除元素时，会自动地根据元素的自然顺序将元素排序，也可以在创建队列时提供Comparator(比较器)来自定义元素顺序。

PriorityQueue类

PriorityQueue类的定义如下：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    // ...
}

可以看到，PriorityQueue继承了AbstractQueue，实现了java.io.Serializable(可序列化接口)，并且泛型类型为E。在PriorityQueue中，所有元素必须实现Comparable接口，并且按照它们的自然顺序排序。也可以创建PriorityQueues(优先队列)时传入一个Comparator对象，用于自定义排序。

构造函数

PriorityQueue类提供了多个构造函数：

public PriorityQueue()
public PriorityQueue(int initialCapacity)
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
public PriorityQueue(Collection<? extends E> c)
public PriorityQueue(PriorityQueue<? extends E> c)
public PriorityQueue(SortedSet<? extends E> c)

第一个构造函数会创建一个初始容量为11的空队列。第二个构造函数将创建具有指定初始容量的空队列。第三个构造函数将创建具有指定初始容量并使用指定比较器的空队列。第四个构造函数将创建一个优先队列，其中包含指定集合中的元素。第五个构造函数将创建与指定优先队列具有相同元素、顺序和容量的新优先队列。第六个构造函数将创建一个优先队列，并包含指定有序集合中的元素。

常用方法

PriorityQueue类提供的方法如下：

public boolean add(E e)
public boolean offer(E e)
public E peek()
public E element()
public E remove()
public E poll()
public boolean remove(Object o)
public int size()
public boolean isEmpty()
public int drainTo(Collection<? super E> c)
public void clear()

其中，add(E e)方法在队列未满时添加指定元素，如果队列已满，则抛出一个IllegalStateException异常。offer(E e)方法与add(E e)方法作用相同，但是在严格执行容量限制时有所不同。如果PriorityQueue满了，offer(E e)方法只是返回false，而不会抛出异常。

peek()方法用于查看此队列的头部(第一个元素)。如果队列为空，则返回null。

Queue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(9);
pq.add(2);
System.out.println(pq.peek()); // 输出2

element()方法与peek()方法作用相同，但是在队列为空时抛出一个NoSuchElementException异常。

remove()方法用于移除此队列的头部(第一个元素)。如果队列为空，则抛出一个NoSuchElementException异常。

Queue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(9);
pq.add(2);
System.out.println(pq.remove()); // 输出2

poll()方法与remove()方法作用相同，但是在队列为空时返回null。

remove(Object o)方法用于移除队列中指定的元素，如果队列中不存在指定的元素，返回false。

Queue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(9);
pq.add(2);
System.out.println(pq.remove(1)); // 输出false

size()方法返回队列中元素的数量。

Queue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(9);
pq.add(2);
System.out.println(pq.size()); // 输出3

isEmpty()方法判断队列是否为空，如果队列为空则返回true，否则返回false。

Queue<Integer> pq = new PriorityQueue<>();
System.out.println(pq.isEmpty()); // 输出true

drainTo(Collection<? super E> c)方法将此队列中所有元素移动到指定集合中，并返回移动的元素数。

Queue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(9);
pq.add(2);
List<Integer> list = new ArrayList<>();
pq.drainTo(list);
System.out.println(list); // 输出[2, 3, 9]

clear()方法用于清空此队列。移除在此队列中的所有元素。

Queue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(9);
pq.add(2);
pq.clear();
System.out.println(pq.size()); // 输出0

案例分析

现在，我们将通过一个案例来了解如何使用PriorityQueue。

题目描述

有一个长度为n的数组a，每次加一个数的时候，将这个数与前k大的数比较一下，如果比前k大的数中最小的还大，则替换最小的数，然后输出当前前k大中的最小的数。

思路分析

可以用一个优先队列来存放前k大的数，如果加入的数小于等于前k大中最小的数，则丢弃这个数；否则将它加入到优先队列中并删除最小的数。

示例代码

以下是实现上述思路的示例代码：

public static void main(String[] args) {
    int n = 10;
    int k = 5;
    int[] a = new int[]{21, 11, 12, 13, 7, 8, 9, 10, 5, 3};
    PriorityQueue<Integer> pq = new PriorityQueue<>(k);

    for(int i = 0; i < n; i++) {
        if(i < k) {
            pq.offer(a[i]);
        } else if(a[i] > pq.peek()) {
            pq.poll();
            pq.offer(a[i]);
        }
        if(i < k - 1) {
            System.out.println(-1);
        } else {
            System.out.println(pq.peek());
        }
    }
}

运行结果：