以下內容轉載至PriorityQueue詳解
概念
PriorityQueue 一個基于優(yōu)先級的無界優(yōu)先級隊列备燃。優(yōu)先級隊列的元素按照其自然順序進行排序，或者根據(jù)構造隊列時提供的 Comparator 進行排序，具體取決于所使用的構造方法少态。該隊列不允許使用 null 元素也不允許插入不可比較的對象(沒有實現(xiàn)Comparable接口的對象)怀偷。
PriorityQueue 隊列的頭指排序規(guī)則最小那哥元素鄙皇。如果多個元素都是最小值則隨機選一個先巴。
PriorityQueue 是一個無界隊列其爵，但是初始的容量(實際是一個Object[])，隨著不斷向優(yōu)先級隊列添加元素伸蚯，其容量會自動擴容摩渺，無需指定容量增加策略的細節(jié)。
基本使用
PriorityQueue使用跟普通隊列一樣剂邮，唯一區(qū)別是PriorityQueue會根據(jù)排序規(guī)則決定誰在隊頭摇幻，誰在隊尾。
往隊列中添加可比較的對象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
}
}
觀察打印結果， 入列：12534绰姻， 出列是12345枉侧， 也是說出列時做了相關判斷，將最小的值返回狂芋。默認情況下PriorityQueue使用自然排序法榨馁，最小元素先出列。
自定義排序規(guī)則
public class Student {
private String name; //名字
private int score; //分數(shù)
//省略getter/setter
}
public class App {
public static void main(String[] args) {
//通過改造器指定排序規(guī)則
PriorityQueue<Student> q = new PriorityQueue<Student>(new Comparator<Student>() {
public int compare(Student o1, Student o2) {
//按照分數(shù)低到高帜矾，分數(shù)相等按名字
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}
}
}
PriorityQueue優(yōu)先級規(guī)則可以由我們根據(jù)具體需求而定制翼虫， 方式有2種：
1>添加元素自身實現(xiàn)了Comparable接口，確保元素是可排序的對象
2>如果添加元素沒有實現(xiàn)Comparable接口屡萤，可以在創(chuàng)建PriorityQueue隊列時直接指定比較器珍剑。
源碼解析
PriorityQueue 是怎么實現(xiàn)優(yōu)先級隊列的呢？
public class PriorityQueue<E> extends AbstractQueue<E>
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的入列操作并沒對所有加入的元素進行優(yōu)先級排序。僅僅保證數(shù)組第一個元素是最小的即可瞳遍。
出列
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;
}
上面源碼闻妓，當?shù)谝粋€元素出列之后，對剩下的元素進行再排序掠械，挑選出最小的元素排在數(shù)組第一個位置由缆。
通過上面源碼，也可看出PriorityQueue并不是線程安全隊列猾蒂，因為offer/poll都沒有對隊列進行鎖定均唉，所以，如果要擁有線程安全的優(yōu)先級隊列肚菠，需要額外進行加鎖操作舔箭。
總結
1>PriorityQueue是一種無界的，線程不安全的隊列
2>PriorityQueue是一種通過數(shù)組實現(xiàn)的蚊逢，并擁有優(yōu)先級的隊列
3>PriorityQueue存儲的元素要求必須是可比較的對象层扶， 如果不是就必須明確指定比較器
