更多 Java 集合類方面的文章，請參見文集《Java 集合類》
優(yōu)先級隊列 PriorityQueue
PriorityQueue 類在 Java 1.5 中引入。
PriorityQueue 是基于優(yōu)先堆的一個無界隊列已脓，這個優(yōu)先隊列中的元素可以默認自然排序或者通過提供的
Comparator 在隊列實例化的時排序。
PriorityQueue 不允許空值通殃，而且不支持 non-comparable（不可比較）的對象度液，比如用戶自定義的類。優(yōu)先隊列要求使用 Java Comparable 和 Comparator 接口給對象排序画舌，并且在排序時會按照優(yōu)先級處理其中的元素堕担。
PriorityQueue 的大小是不受限制的，但在創(chuàng)建時可以指定初始大小曲聂。當(dāng)我們向優(yōu)先隊列增加元素的時候霹购，隊列大小會自動增加。
PriorityQueue 是非線程安全的朋腋，所以 Java 提供了 PriorityBlockingQueue（實現(xiàn) BlockingQueue接口）用于Java 多線程環(huán)境齐疙。
示例：
public class PriorityQueueTest {
public static void main(String[] args) {
Queue<Integer> queue1 = new PriorityQueue<Integer>();
queue1.add(2);
queue1.add(1);
queue1.add(3);
while (!queue1.isEmpty()) {
Integer i = queue1.poll();
System.out.println(i);
}
Comparator<Student> comparator = new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return (o1.id - o2.id);
}
};
Queue<Student> queue2 = new PriorityQueue<Student>(comparator);
queue2.add(new Student(2, "B"));
queue2.add(new Student(1, "A"));
queue2.add(new Student(3, "C"));
while (!queue2.isEmpty()) {
Student s = queue2.poll();
System.out.println(s.toString());
}
}
public static class Student {
private int id;
private String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
public String toString() {
return id + "-" + name;
}
}
}
輸出：
1
2
3
1-A
2-B
3-C
優(yōu)先級隊列 PriorityQueue 的實現(xiàn)原理
通過堆實現(xiàn)，具體說是通過完全二叉樹（complete binary tree）實現(xiàn)的小頂堆（任意一個非葉子節(jié)點的權(quán)值，都不大于其左右子節(jié)點的權(quán)值），也就意味著可以通過數(shù)組來作為 PriorityQueue 的底層實現(xiàn)睹耐。
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
*/
private int size = 0;
父子節(jié)點的編號之間有如下關(guān)系：
- leftNo = parentNo * 2 + 1
- rightNo = parentNo * 2 + 2
- parentNo = (nodeNo - 1) / 2
add(E e) 和 offer(E e) 操作的時間復(fù)雜度為 log(N)：
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;
}
poll() 操作的時間復(fù)雜度為 log(N)：
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;
}
peek() 操作的時間復(fù)雜度為 O(1)：
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
優(yōu)先級隊列 PriorityQueue 的使用場景
求 Top K 大的元素
維護數(shù)據(jù)流中的中位數(shù)
