Java优先队列（PriorityQueue）

我们知道队列是遵循先进先出（First-In-First-Out）模式的，但有些时候需要在队列中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue(优先队列)会很有帮助。PriorityQueue类的特点：

1. 在Java1.5中引入并作为 Java Collections Framework 的一部分
2. 基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。（不指定Comparator时默认为最小堆），优先队列的头是基于自然排序或者Comparator排序的最小元素。堆排序只能保证根是最大（最小），整个堆并不是有序的
3. 优先队列不允许空值
4. 不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序
5. PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境
6. 优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加

我们有一个用户类Customer，它没有提供任何类型的排序。当我们用它建立优先队列时，应该为其提供一个比较器对象。

Customer.java

package com.journaldev.collections; 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对象。

下面是最终的测试代码，展示如何使用PriorityQueue：

PriorityQueueExample.java

package com.journaldev.collections; 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) { //优先队列自然排序示例 Queue 
  
    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); } //优先队列使用示例 Queue 
   
     customerPriorityQueue = new PriorityQueue<>(7, idComparator); addDataToQueue(customerPriorityQueue); pollDataFromQueue(customerPriorityQueue); } //匿名Comparator实现 public static Comparator 
    
      idComparator = new Comparator 
     
       (){ @Override public int compare(Customer c1, Customer c2) { return (int) (c1.getId() - c2.getId()); } }; //用于往队列增加数据的通用方法 private static void addDataToQueue(Queue 
      
        customerPriorityQueue) { Random rand = new Random(); for(int i=0; i<7; i++){ int id = rand.nextInt(100); customerPriorityQueue.add(new Customer(id, "Pankaj "+id)); } } //用于从队列取数据的通用方法 private static void pollDataFromQueue(Queue 
       
         customerPriorityQueue) { while(true){ Customer cust = customerPriorityQueue.poll(); if(cust == null) break; System.out.println("Processing Customer with ID="+cust.getId()); } } } 
        
       
      
     
    
  

注意我用实现了Comparator接口的Java匿名类，并且实现了基于id的比较器。

当我运行以上测试程序时，我得到以下输出：

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 

从输出结果可以清楚的看到，最小的元素在队列的头部因而最先被取出。如果不实现Comparator，在建立customerPriorityQueue时会抛出ClassCastException。

Exception in thread "main" java.lang.ClassCastException: com.journaldev.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.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45) at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25) 

总结：

注意1：该队列是用数组实现，但是数组大小可以动态增加，容量无限。

注意2：队列的实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue实例。保证线程安全可以使用PriorityBlockingQueue 类。

注意3：不允许使用 null 元素。

注意4：插入方法（offer()、poll()、remove() 、add() 方法）时间复杂度为O(log(n)) ；
remove(Object) 和 contains(Object) 时间复杂度为O(n)；
检索方法（peek、element 和 size）时间复杂度为常量。

注意7：此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。

利用 优先队列 求数组中前k个最小的数字，时间复杂度：O（nlogk）
更多解法相见
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

/* 用最大堆保存这k个数，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。 最大堆 时间复杂度O（nlogk） */ public ArrayList 
  
    GetLeastNumbers_Solution(int[] input, int k) { ArrayList 
   
     res = new ArrayList<>(); //这里不要忘了判断 k>input.length if (input == null || input.length == 0 || k <= 0 || k > input.length) { return res; } PriorityQueue 
    
      maxHeap = new PriorityQueue<>(k, new Comparator 
     
       () { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); for (int i = 0; i < input.length; i++) { if (maxHeap.size() != k) { maxHeap.offer(input[i]); } else if (input[i] < maxHeap.peek()) { maxHeap.poll(); maxHeap.offer(input[i]); } } for (int num : maxHeap) { res.add(num); } return res; }