PriorityQueue也是集合框架中定义的类,它为我们提供了一种基于优先级处理对象的方法。
前面已经描述了对象的插入和删除在Java队列中遵循FIFO模式。然而,有时需要根据优先级处理队列的元素,这就是PriorityQueue发挥作用的地方。
PriorityQueue基于优先级堆。优先级队列的元素按照自然顺序排序,或者由队列构造时提供的Comparator排序,这取决于使用的是哪个构造函数。
1.1 PriorityQueue 层次结构 1.2 PriorityQueue类声明让我们看看java.util.PriorityQueue类的声明。
public class PriorityQueue1.3 PriorityQueue 的特性extends AbstractQueue implements Serializable
优先级队列的几个重要点如下:
- PriorityQueue不允许为空。
- 我们不能创建一个不可比较的对象的优先级队列
- PriorityQueue是未绑定队列。
- 这个队列的头是相对于指定顺序最小的元素。如果多个元素为最小值绑定,则头部是这些元素中的一个——绑定被任意打破。
- 由于PriorityQueue不是线程安全的,java提供了PriorityBlockingQueue类,它实现了在java多线程环境中使用的BlockingQueue接口。
- 队列检索操作轮询、删除、查看和元素访问队列头部的元素。
- 它为添加和轮询方法提供O(log(n))时间。
- 它从AbstractQueue、AbstractCollection、Collection和Object类继承方法。
- PriorityQueue():创建一个具有默认初始容量(11)的PriorityQueue,它根据元素的自然顺序对其进行排序。
private static final int DEFAULT_INITIAL_CAPACITY = 11; public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); }
- PriorityQueue(Collection
c):创建一个包含指定集合中的元素的PriorityQueue。
PriorityQueuepq = new PriorityQueue (Collection c);
- PriorityQueue(int initialCapacity):创建一个具有指定初始容量的PriorityQueue,根据元素的自然顺序对其进行排序。
PriorityQueuepq = new PriorityQueue (int initialCapacity);
- PriorityQueue(int initialCapacity, Comparator Comparator):创建一个具有指定初始容量的PriorityQueue,根据指定的比较器对其元素进行排序。
PriorityQueuepq = new PriorityQueue(int initialCapacity, Comparator comparator);
- PriorityQueue(PriorityQueue c):创建一个包含指定优先级队列中的元素的PriorityQueue。
PriorityQueuepq = new PriorityQueue(PriorityQueue c);
- PriorityQueue(SortedSet c):创建一个包含指定排序集中的元素的PriorityQueue。
PriorityQueue1.3 PriorityQueue 的 基本操作pq = new PriorityQueue (SortedSet c);
例子:下面的示例解释了优先级队列的以下基本操作。
- boolean add(E元素):该方法将指定的元素插入到优先级队列中。
- public peek():这个方法检索队列的头部,但不删除,如果队列为空则返回null。
- public poll():该方法检索并删除该队列的头部,如果该队列为空,则返回null。
// 创建优先队列 PriorityQueuepQueue = new PriorityQueue (); // 添加元素 pQueue.add(10); pQueue.add(20); pQueue.add(15); System.out.println("初始优先队列:"+pQueue); // 检索队列的头部,但不删除 System.out.println(pQueue.peek()); // 检索队列的头部,并删除 System.out.println(pQueue.poll()); // 打印头部元素 System.out.println(pQueue.peek()); System.out.println("最终优先队列:"+pQueue);
输出
初始优先队列:[10, 20, 15] 10 10 15 最终优先队列:[15, 20]二、PriorityQueue 的操作
让我们看看如何在Priority Queue类上执行一些常用操作。
2.1 添加操作为了在优先队列中添加元素,可以使用add()方法。插入顺序不保留在PriorityQueue中。元素按照优先级顺序存储,默认情况下优先级为升序。
PriorityQueuepq = new PriorityQueue<>(); for(int i=0;i<3;i++){ pq.add(i); pq.add(1); } System.out.println(pq);
输出
[0, 1, 1, 1, 2, 1]
我们不会通过打印PriorityQueue来获得已排序的元素。
2.2 删除操作为了从优先队列中删除一个元素,可以使用remove()方法。
如果有多个这样的对象,则删除第一个出现的对象。除此之外,poll()方法还用于删除头部并返回它。
Queuepq = new PriorityQueue<>(); pq.add("广州"); pq.add("深圳"); pq.add("北京"); System.out.println("初始 队列 " + pq); pq.remove("深圳"); System.out.println("删除后 " + pq); System.out.println("删除头队列:" + pq.poll()); System.out.println("最终队列 " + pq);
初始 队列 [北京, 深圳, 广州] 删除后 [北京, 广州] 删除头队列:北京 最终队列 [广州]2.3 访问操作
由于Queue遵循先进先出原则,我们只能访问队列的头部。
要访问优先级队列中的元素,可以使用peek()方法。
PriorityQueuepq = new PriorityQueue<>(); pq.add("广州"); pq.add("深圳"); pq.add("东莞"); System.out.println("PriorityQueue: " + pq); // 使用peek方法,访问头部 String element = pq.peek(); System.out.println("访问元素: " + element);
输出
PriorityQueue: [东莞, 深圳, 广州] 访问元素: 东莞2.4 迭代操作
有多种方法可以遍历PriorityQueue。最著名的方法是将队列转换为数组并使用for循环遍历。
但是,队列还有一个内置迭代器,可用于遍历队列。
PriorityQueuepq = new PriorityQueue<>(); pq.add("广州"); pq.add("深圳"); pq.add("东莞"); System.out.println("PriorityQueue: " + pq); // 转换为数组 遍历 for (Object o : pq.toArray()) { System.out.println(o); } // 内置迭代器 Iterator iterator = pq.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); }
输出
PriorityQueue: [东莞, 深圳, 广州] 东莞 深圳 广州 东莞 深圳 广州