极客笔记Java中的PriorityQueue poll()方法
PriorityQueue是Java中非常常见的数据结构之一，它可以用来实现一个最小堆或者最大堆，可以在常数时间内对元素进行插入和查询，而且不需要初始化一个固定大小的数组来保存元素。这是一个非常便利的数据结构，因此它被广泛地应用在各种场合中。
PriorityQueue的一个特殊方法是poll()，它的作用是向外部获取队列中的第一个元素，然后将其从队列中删除。这个特殊方法的实现非常高效，在时间复杂度上仅仅为O(log n)，通常情况下，PriorityQueue中元素是按照自然顺序排列的，或者是按照某个特定的比较器排列的。
Priority Queue的基础概念及实例
在Java中，Priority Queue（优先级队列）是通过一个完整的实现公式来实现的：
PriorityQueue<E> pq = new PriorityQueue<>(initialCapacity, Comparator<? super E>);
其中，initialCapacity代表你想要预先分配的队列空间，而Comparator<? super E>代表一种比较器，可以通过这个比较器来确定元素的排序方式。如果你没有指定比较器，那么队列默认采用元素自身所实现的比较方式，如果元素没有实现比较方式，那么当你试图对队列中的元素进行排序时，往往会抛出ClassCastException的异常。
我们简单地来看一个PriorityQueue代码的例子，示例代码如下：
import java.util.PriorityQueue;
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(1);
pq.add(5);
pq.add(3);
pq.add(2);
pq.add(4);
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
在上面的示例代码中，如何将几个整数元素加入Priority Queue中，然后依次弹出并打印出它们。这段代码的输出结果如下：
1
2
3
4
5
事实上，如果你没有指定比较器，Priority Queue默认使用元素自身所提供的compareTo方法（如果元素实现了Comparable接口），所以可以省略掉构造方法的第二个参数，示例如下：
import java.util.PriorityQueue;
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(1);
pq.add(5);
pq.add(3);
pq.add(2);
pq.add(4);
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
PriorityQueue的poll()方法
在PriorityQueue中，poll()方法的作用是从队列中获取并删除队列的头结点元素（即队列中优先级最高的元素）。作为队列的一个基本操作，poll()其实有很多场景是被广泛使用的，比如优先级队列和工作队列等。
在Java中，Priority Queue的实现是使用了一个基于二叉堆的数据结构，二叉堆相当于一个近似的完全二叉树，由于它是一个平衡的二叉树，所以插入和删除的时间复杂度都是O(log n)级别的。
下面是一个示例代码，它使用了Priority Queue的poll()方法来实现一个工作队列，当队列中存在工作时，从队列头部获取并处理一个工作任务。示例代码如下：
import java.util.PriorityQueue;
public class WorkQueue {
private PriorityQueue<Runnable> queue = new PriorityQueue<>();
public synchronized void addTask(Runnable task) {
queue.add(task);
}
public synchronized void doNextTask() {
if (!queue.isEmpty()) {
queue.poll().run();
}
}
}
在上面的代码中，我们创建了一个WorkQueue类，它有两个方法：addTask和doNextTask。addTask方法用于向队列中添加一个任务，而doNextTask方法则从队列头部获取并执行一个任务。
在addTask方法中，我们使用PriorityQueue的add()方法将一个任务加入队列中。在doNextTask方法中，如果队列不为空，我们使用PriorityQueue的poll()方法从队列头部获取并删除一个任务，然后执行这个任务的run()方法。
PriorityQueue的poll()方法的示例代码
我们再来看一个示例代码，它演示了如何使用PriorityQueue的poll()方法来实现一个最大堆。在这个示例代码中，我们定义了一个最大堆类MaxHeap，它有两个基本方法：add和removeMax。其中，add方法将元素加入堆中，而removeMax方法则从堆中删除最大元素。示例代码如下：
import java.util.PriorityQueue;
public class MaxHeap {
private PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
public void add(int num) {
pq.add(num);
}
public int removeMax() {
return pq.poll();
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap();
heap.add(10);
heap.add(20);
heap.add(5);
System.out.println(heap.removeMax()); // 20
System.out.println(heap.removeMax()); // 10
}
}
在上面的代码中，我们定义了一个私有成员变量pq，它是一个PriorityQueue类型的变量，而且我们将它初始化为一个最大堆，因为我们使用了一个比较器，它的比较方式是b – a，这意味着我们想要从PriorityQueue中移除最大的元素。
在add方法中，我们直接调用PriorityQueue的add方法将元素加入堆中。在removeMax方法中，我们使用PriorityQueue的poll方法从优先队列中获取并弹出最大元素，因为PriorityQueue本身支持O(log n)的弹出操作，所以这个方法的效率非常高。
最后，在main方法中，我们创建了一个MaxHeap实例，向其中加入了三个整数元素，然后依次调用了removeMax方法并打印返回的结果，我们可以看到最大元素依次是20和10。
结论
通过这篇文章的介绍，我们了解了Java中Priority Queue的基本概念及其重要方法poll()的使用方式。Priority Queue是一个非常实用的数据结构，它支持快速的插入和删除操作，而且具有自我调整平衡的能力，非常适用于实现顺序队列等操作。如果读者想要深入学习Java的Priority Queue，建议通过实践编写更多的代码来深化和巩固自己的知识。