PriorityQueue
我们知道Queue是遵循先进先出（First-In-First-Out）模式的，但有些时候需要在Queue中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue会很有帮助。
PriorityQueue能高效地插入元素，高效地删除最小元素
删除是基于默认的自然顺序排列（也就是数字小的在队列头）或者按Comparator规定的顺序排列
| 最大/最小 | 加入新元素 | 删除极值 | 删除指定元素 | 查找指定元素 | 查找极值 |
|---|---|---|---|---|---|
| Heap | o(lgn) | o(lgn) | o(n) | o(n) | o(1)一头 |
比如说，Sue有一些轻微的小伤口最先来到了医院的急诊室
虽然Sue是先来的，但是，Joe被蛇咬伤更加需要先治疗，于是Joe被排在了Sue的前面
public static void main(String[] args){
PriorityQueue<String> pQueue = new PriorityQueue<>();
pQueue.add("B");
pQueue.offer("C");
pQueue.add("F");
pQueue.offer("A");
pQueue.add("L");
pQueue.add("D");
pQueue.add("E");
pQueue.add("J");
System.out.println("Head:" + pQueue.peek());
while(!pQueue.isEmpty()){
System.out.print(pQueue.poll() + " ");
}
}
输出：
Head: A
A B C D E F J L
从以上代码可以看出，即使add到PriorityQueue的顺序是乱序，但PriorityQueue会以默认的从小到大顺序被poll()出来
public static void main(String[] args){
PriorityQueue<String> pQueue = new PriorityQueue<>();
pQueue.add("B");
pQueue.offer("C");
pQueue.add("F");
pQueue.offer("A");
pQueue.add("L");
pQueue.add("D");
pQueue.add("E");
pQueue.add("J");
while(!pQueue.isEmpty()){
System.out.println(pQueue);
System.out.println("After calling pQueue.remove(),it removed: " + pQueue.remove());
System.out.println(pQueue);
System.out.println("-------------------------------");
}
}
输出：
// 直接打印PriorityQueue内部的元素，会很奇怪（并不是字母排序）。 因为内部是按binary heap顺序来打印的
[A, B, D, C, L, F, E, J]
After calling pQueue.remove(),it removed: A
[B, C, D, J, L, F, E]
-------------------------------
[B, C, D, J, L, F, E]
After calling pQueue.remove(),it removed: B
[C, E, D, J, L, F]
-------------------------------
[C, E, D, J, L, F]
After calling pQueue.remove(),it removed: C
[D, E, F, J, L]
-------------------------------
[D, E, F, J, L]
After calling pQueue.remove(),it removed: D
[E, J, F, L]
-------------------------------
[E, J, F, L]
After calling pQueue.remove(),it removed: E
[F, J, L]
-------------------------------
[F, J, L]
After calling pQueue.remove(),it removed: F
[J, L]
-------------------------------
[J, L]
After calling pQueue.remove(),it removed: J
[L]
-------------------------------
[L]
After calling pQueue.remove(),it removed: L
[]
-------------------------------
以下代码可以看出，虽然被remove()出来是按照PriorityQueue会以默认的从小到大顺序，但将PriorityQueue的内部打印出来会很奇怪（并不是字母顺序）因为内部是binary heap顺序打印的