我们知道队列遵循先进先出(First-In-First-Out)模型,但有时需要根据优先级处理队列中的对象。那么可使用Java PriorityQueue对象来实现。
例如,假设有一个应用程序可以为每日交易时段生成股票报告。应用程序处理大量数据并需要时间来处理它。因此,客户向实际排队的应用程序发送请求,但希望先处理高级客户,然后再处理标准客户。所以在这种情况下,java中的PriorityQueue
类实现就非常有用了。
Java优先级队列
PriorityQueue
类是在Java 1.5中引入的,它是Java Collections框架的一部分。
PriorityQueue
类是基于优先级堆的无界队列,优先级队列的元素默认按自然顺序排序。我们可以在实例化优先级队列时提供比较器以进行排序。
Java优先级队列不允许空值,无法创建不可比较的PriorityQueue
对象。我们使用java Comparable
和Comparator
对对象进行排序,优先级队列使用它们来优先处理它的元素。
优先级队列的头部是基于自然排序或基于比较器的排序的最小元素,如果有多个具有相同排序的对象,则它可以随机轮询其中任何一个。当我们轮询队列时,从队列中返回排在头部的对象。
Java优先级队列大小是无限制的,但可以在创建时指定初始容量。当向优先级队列添加元素时,它的容量会自动增长。
PriorityQueue
不是线程安全的,因此java提供了PriorityBlockingQueue
类,它实现了在java多线程环境中使用的BlockingQueue
接口。
Java优先级队列实现为enqueing
和dequeing
方法提供了O(log(n))时间。
下面来看看Java PriorityQueue
以及Comparator
自然排序的示例。
自定义类Customer
不提供任何类型的排序,因此当它与PriorityQueue
一起使用时,应该为它提供一个比较器对象。
public class Customer {
private int id;
private String name;
public Customer(int i, String n){
this.id=i;
this.name=n;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
}
我们将使用java随机数生成来生成随机客户对象。对于自然排序,这里将使用Integer
数据类型,它也是一个java包装类。
下面是最终测试代码,演示了如何在java中使用优先级队列。
文件:PriorityQueueExample.java
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
public class PriorityQueueExample {
public static void main(String[] args) {
//natural ordering example of priority queue
Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
Random rand = new Random();
for(int i=0;i<7;i++){
integerPriorityQueue.add(new Integer(rand.nextInt(100)));
}
for(int i=0;i<7;i++){
Integer in = integerPriorityQueue.poll();
System.out.println("Processing Integer:"+in);
}
//PriorityQueue example with Comparator
Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
addDataToQueue(customerPriorityQueue);
pollDataFromQueue(customerPriorityQueue);
}
//Comparator anonymous class implementation
public static Comparator<Customer> idComparator = new Comparator<Customer>(){
@Override
public int compare(Customer c1, Customer c2) {
return (int) (c1.getId() - c2.getId());
}
};
//utility method to add random data to Queue
private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
Random rand = new Random();
for(int i=0; i<7; i++){
int id = rand.nextInt(100);
customerPriorityQueue.add(new Customer(id, "Pankaj "+id));
}
}
//utility method to poll data from queue
private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
while(true){
Customer cust = customerPriorityQueue.poll();
if(cust == null) break;
System.out.println("Processing Customer with ID="+cust.getId());
}
}
}
请注意,使用java匿名类来实现Comparator
接口并创建基于id
的比较器。当运行java优先级队列示例测试程序时,它会生成以下输出。
Processing Integer:9
Processing Integer:16
Processing Integer:18
Processing Integer:25
Processing Integer:33
Processing Integer:75
Processing Integer:77
Processing Customer with ID=6
Processing Customer with ID=20
Processing Customer with ID=24
Processing Customer with ID=28
Processing Customer with ID=29
Processing Customer with ID=82
Processing Customer with ID=96
从输出中可以清楚地看出,最小元素处于首位,并首先进行了轮询。如果在创建customerPriorityQueue
时不提供比较器,它将在运行时抛出ClassCastException
异常。
Exception in thread "main" java.lang.ClassCastException: com.yiibai.collections.Customer cannot be cast to java.lang.Comparable
at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
at java.util.PriorityQueue.offer(PriorityQueue.java:329)
at java.util.PriorityQueue.add(PriorityQueue.java:306)
at com.yiibai.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
at com.yiibai.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)