PriorityQueue詳解

概念

PriorityQueue 一個基於優先級的無界優先級隊列。優先級隊列的元素按照其自然順序進行排序，或者根據構造隊列時提供的 Comparator 進行排序，具體取決於所使用的構造方法。該隊列不允許使用 null 元素也不允許插入不可比較的對象(沒有實現Comparable接口的對象)。

PriorityQueue 隊列的頭指排序規則最小那哥元素。如果多個元素都是最小值則隨機選一個。

PriorityQueue 是一個無界隊列，但是初始的容量(實際是一個Object[])，隨著不斷向優先級隊列添加元素，其容量會自動擴容，無需指定容量增加策略的細節。

基本使用

PriorityQueue使用跟普通隊列一樣，唯一區別是PriorityQueue會根據排序規則決定誰在隊頭，誰在隊尾。

往隊列中添加可比較的對象String

public class App {
 public static void main(String[] args) {
 PriorityQueue<string> q = new PriorityQueue<string>();
 //入列
 q.offer("1");
 q.offer("2");
 q.offer("5");
 q.offer("3");
 q.offer("4");
 //出列
 System.out.println(q.poll()); //1
 System.out.println(q.poll()); //2
 System.out.println(q.poll()); //3
 System.out.println(q.poll()); //4
 System.out.println(q.poll()); //5
 }
}
/<string>/<string>

觀察打印結果， 入列：12534， 出列是12345， 也是說出列時做了相關判斷，將最小的值返回。默認情況下PriorityQueue使用自然排序法，最小元素先出列。

自定義排序規則

public class Student {
 private String name; //名字
 private int score; //分數
 //省略getter/setter
} 

public class App {
 public static void main(String[] args) {
 //通過改造器指定排序規則
 PriorityQueue<student> q = new PriorityQueue<student>(new Comparator<student>() {
 public int compare(Student o1, Student o2) {
 //按照分數低到高，分數相等按名字
 if(o1.getScore() == o2.getScore()){
 return o1.getName().compareTo(o2.getName());
 }
 return o1.getScore() - o2.getScore();
 }
 });
 //入列
 q.offer(new Student("dafei", 20));
 q.offer(new Student("will", 17));
 q.offer(new Student("setf", 30));
 q.offer(new Student("bunny", 20));
 //出列
 System.out.println(q.poll()); //Student{name='will', score=17}
 System.out.println(q.poll()); //Student{name='bunny', score=20}
 System.out.println(q.poll()); //Student{name='dafei', score=20}
 System.out.println(q.poll()); //Student{name='setf', score=30}
 }
}
/<student>/<student>/<student>

PriorityQueue優先級規則可以由我們根據具體需求而定製， 方式有2種：

1>添加元素自身實現了Comparable接口，確保元素是可排序的對象

2>如果添加元素沒有實現Comparable接口，可以在創建PriorityQueue隊列時直接指定比較器。

源碼解析

PriorityQueue 是怎麼實現優先級隊列的呢？

public class PriorityQueue extends AbstractQueue
 implements java.io.Serializable {
 transient Object[] queue; //隊列容器， 默認是11
 private int size = 0; //隊列長度
 private final Comparator super E> comparator; //隊列比較器， 為null使用自然排序
 //....
}

入列

 public boolean offer(E e) {
 if (e == null)
 throw new NullPointerException();
 modCount++;
 int i = size;
 if (i >= queue.length)
 grow(i + 1); //當隊列長度大於等於容量值時，自動拓展
 size = i + 1;
 if (i == 0)
 queue[0] = e;
 else
 siftUp(i, e); //
 return true;
 }
 private void siftUp(int k, E x) {
 if (comparator != null)
 siftUpUsingComparator(k, x); //指定比較器
 else
 siftUpComparable(k, x); //沒有指定比較器，使用默認的自然比較器
 }
 private void siftUpComparable(int k, E x) {
 Comparable super E> key = (Comparable super E>) x;
 while (k > 0) {
 int parent = (k - 1) >>> 1;
 Object e = queue[parent];
 if (key.compareTo((E) e) >= 0)
 break;
 queue[k] = e;
 k = parent; 

 }
 queue[k] = key;
 }
 private void siftUpUsingComparator(int k, E x) {
 while (k > 0) {
 int parent = (k - 1) >>> 1;
 Object e = queue[parent];
 if (comparator.compare(x, (E) e) >= 0)
 break;
 queue[k] = e;
 k = parent;
 }
 queue[k] = x;
 }

這裡自作簡單比較，使用選擇排序法將入列的元素放左邊或者右邊.

從源碼上看PriorityQueue的入列操作並沒對所有加入的元素進行優先級排序。僅僅保證數組第一個元素是最小的即可。

出列

 public E poll() {
 if (size == 0)
 return null;
 int s = --size;
 modCount++;
 E result = (E) queue[0];
 E x = (E) queue[s];
 queue[s] = null;
 if (s != 0)
 siftDown(0, x);
 return result;
 }
 private void siftDown(int k, E x) {
 if (comparator != null)
 siftDownUsingComparator(k, x); //指定比較器
 else
 siftDownComparable(k, x); //默認比較器
 }
private void siftDownComparable(int k, E x) {
 Comparable super E> key = (Comparable super E>)x; 

 int half = size >>> 1; // loop while a non-leaf
 while (k < half) {
 int child = (k << 1) + 1; // assume left child is least
 Object c = queue[child];
 int right = child + 1;
 if (right < size &&
 ((Comparable super E>) c).compareTo((E) queue[right]) > 0)
 c = queue[child = right];
 if (key.compareTo((E) c) <= 0)
 break;
 queue[k] = c;
 k = child;
 }
 queue[k] = key;
 }
 @SuppressWarnings("unchecked")
 private void siftDownUsingComparator(int k, E x) {
 int half = size >>> 1;
 while (k < half) {
 int child = (k << 1) + 1;
 Object c = queue[child];
 int right = child + 1;
 if (right < size &&
 comparator.compare((E) c, (E) queue[right]) > 0)
 c = queue[child = right];
 if (comparator.compare(x, (E) c) <= 0)
 break;
 queue[k] = c;
 k = child;
 }
 queue[k] = x;
 }

上面源碼，當第一個元素出列之後，對剩下的元素進行再排序，挑選出最小的元素排在數組第一個位置。

通過上面源碼，也可看出PriorityQueue並不是線程安全隊列，因為offer/poll都沒有對隊列進行鎖定，所以，如果要擁有線程安全的優先級隊列，需要額外進行加鎖操作。

1>PriorityQueue是一種無界的，線程不安全的隊列

2>PriorityQueue是一種通過數組實現的，並擁有優先級的隊列

3>PriorityQueue存儲的元素要求必須是可比較的對象， 如果不是就必須明確指定比較器

閱讀更多 叩丁狼stef 的文章

關鍵字: 軟件 詳解 優先級