更多 Java 集合类方面的文章，请参见文集《Java 集合类》
优先级队列 PriorityQueue
PriorityQueue 类在 Java 1.5 中引入。
PriorityQueue 是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的
Comparator 在队列实例化的时排序。
PriorityQueue 不允许空值，而且不支持 non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用 Java Comparable 和 Comparator 接口给对象排序，并且在排序时会按照优先级处理其中的元素。
PriorityQueue 的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
PriorityQueue 是非线程安全的，所以 Java 提供了 PriorityBlockingQueue（实现 BlockingQueue接口）用于Java 多线程环境。
示例：
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
优先级队列 PriorityQueue 的实现原理
通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为 PriorityQueue 的底层实现。
/**
* 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;
父子节点的编号之间有如下关系：
- leftNo = parentNo * 2 + 1
- rightNo = parentNo * 2 + 2
- parentNo = (nodeNo - 1) / 2
add(E e) 和 offer(E e) 操作的时间复杂度为 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() 操作的时间复杂度为 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() 操作的时间复杂度为 O(1)：
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
