解析Java中PriorityQueue优先级队列结构的源码及用法
一、priorityqueue的数据结构
jdk7中priorityqueue（优先级队列）的数据结构是二叉堆。准确的说是一个最小堆。
二叉堆是一个特殊的堆， 它近似完全二叉树。二叉堆满足特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
下图是一个最大堆
priorityqueue队头就是给定顺序的最小元素。
priorityqueue不允许空值且不支持non-comparable的对象。priorityqueue要求使用comparable和comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。
priorityqueue的大小是无限制的（unbounded）, 但在创建时可以指定初始大小。当增加队列元素时，队列会自动扩容。
priorityqueue不是线程安全的， 类似的priorityblockingqueue是线程安全的。
我们知道队列是遵循先进先出（first-in-first-out）模式的，但有些时候需要在队列中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，java的priorityqueue(优先队列)会很有帮助。
priorityqueue是基于优先堆的一个*队列，这个优先队列中的元素可以默认自然排序或者通过提供的comparator（比较器）在队列实例化的时排序。
优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用java comparable和comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。
优先队列的头是基于自然排序或者comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。
优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
priorityqueue是非线程安全的，所以java提供了priorityblockingqueue（实现blockingqueue接口）用于java多线程环境。
二、priorityqueue源码分析
成员：
priavte transient object[] queue; private int size = 0;
1.priorityqueue构造小顶堆的过程
这里我们以priorityqueue构造器传入一个容器为参数priorityqueue(collecntion<? extends e>的例子：
构造小顶堆的过程大体分两步：
复制容器数据，检查容器数据是否为null
private void initelementsfromcollection(collection<? extends e> c) {
object[] a = c.toarray();
// if c.toarray incorrectly doesn't return object[], copy it.
if (a.getclass() != object[].class)
a = arrays.copyof(a, a.length, object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new nullpointerexception();
this.queue = a;
this.size = a.length;
}
调整，使数据满足小顶堆的结构。
首先介绍两个调整方式siftup和siftdown
siftdown: 在给定初始化元素的时候，要调整元素，使其满足最小堆的结构性质。因此不停地从上到下将元素x的键值与孩子比较并做交换，直到找到元素x的键值小于等于孩子的键值（即保证它比其左右结点值小），或者是下降到叶子节点为止。
例如如下的示意图，调整9这个节点：
private void siftdowncomparable(int k, e x) {
comparable<? super e> key = (comparable<? super e>)x;
int half = size >>> 1; // size/2是第一个叶子结点的下标
//只要没到叶子节点
while (k < half) {
int child = (k << 1) + 1; // 左孩子
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;
}
siftup: priorityqueue每次新增加一个元素的时候是将新元素插入对尾的。因此，应该与siftdown有同样的调整过程，只不过是从下（叶子）往上调整。
例如如下的示意图，填加key为3的节点：
private void siftupcomparable(int k, e x) {
comparable<? super e> key = (comparable<? super e>) x;
while (k > 0) {
int parent = (k - 1) >>> 1; //获取parent下标
object e = queue[parent];
if (key.compareto((e) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
总体的建立小顶堆的过程就是：
private void initfromcollection(collection<? extends e> c) {
initelementsfromcollection(c);
heapify();
}
其中heapify就是siftdown的过程。
2.priorityqueue容量扩容过程
从实例成员可以看出，priorityqueue维护了一个object[], 因此它的扩容方式跟顺序表arraylist相差不多。
这里只给出grow方法的源码
private void grow(int mincapacity) {
int oldcapacity = queue.length;
// double size if small; else grow by 50%
int newcapacity = oldcapacity + ((oldcapacity < 64) ?
(oldcapacity + 2) :
(oldcapacity >> 1));
// overflow-conscious code
if (newcapacity - max_array_size > 0)
newcapacity = hugecapacity(mincapacity);
queue = arrays.copyof(queue, newcapacity);
}
可以看出，当数组的capacity不大的时候，每次扩容也不大。当数组容量大于64的时候，每次扩容double。
三、priorityqueue的应用
eg1：
这里给出一个最简单的应用：从动态数据中求第k个大的数。
思路就是维持一个size = k 的小顶堆。
//data是动态数据
//heap维持动态数据的堆
//res用来保存第k大的值
public boolean kthlargest(int data, int k, priorityqueue<integer> heap, int[] res) {
if(heap.size() < k) {
heap.offer(data);
if(heap.size() == k) {
res[0] = heap.peek();
return true;
}
return false;
}
if(heap.peek() < data) {
heap.poll();
heap.offer(data);
}
res[0] = heap.peek();
return true;
}
eg2：
我们有一个用户类customer，它没有提供任何类型的排序。当我们用它建立优先队列时，应该为其提供一个比较器对象。
customer.java
package com.journaldev.collections;
public class customer {
private int id;
private string name;
public customer(int i, string n){
this.id=i;
this.name=n;
}
public int getid() {
return id;
}
public string getname() {
return name;
}
}
我们使用java随机数生成随机用户对象。对于自然排序，我们使用integer对象，这也是一个封装过的java对象。
下面是最终的测试代码，展示如何使用priorityqueue：
priorityqueueexample.java
package com.journaldev.collections;
import java.util.comparator;
import java.util.priorityqueue;
import java.util.queue;
import java.util.random;
public class priorityqueueexample {
public static void main(string[] args) {
//优先队列自然排序示例
queue<integer> integerpriorityqueue = new priorityqueue<>(7);
random rand = new random();
for(int i=0;i<7;i++){
integerpriorityqueue.add(new integer(rand.nextint(100)));
}
for(int i=0;i<7;i++){
integer in = integerpriorityqueue.poll();
system.out.println("processing integer:"+in);
}
//优先队列使用示例
queue<customer> customerpriorityqueue = new priorityqueue<>(7, idcomparator);
adddatatoqueue(customerpriorityqueue);
polldatafromqueue(customerpriorityqueue);
}
//匿名comparator实现
public static comparator<customer> idcomparator = new comparator<customer>(){
@override
public int compare(customer c1, customer c2) {
return (int) (c1.getid() - c2.getid());
}
};
//用于往队列增加数据的通用方法
private static void adddatatoqueue(queue<customer> customerpriorityqueue) {
random rand = new random();
for(int i=0; i<7; i++){
int id = rand.nextint(100);
customerpriorityqueue.add(new customer(id, "pankaj "+id));
}
}
//用于从队列取数据的通用方法
private static void polldatafromqueue(queue<customer> customerpriorityqueue) {
while(true){
customer cust = customerpriorityqueue.poll();
if(cust == null) break;
system.out.println("processing customer with id="+cust.getid());
}
}
}
注意我用实现了comparator接口的java匿名类，并且实现了基于id的比较器。
当我运行以上测试程序时，我得到以下输出：
processing integer:9 processing integer:16 processing integer:18 processing integer:25 processing integer:33 processing integer:75 processing integer:77 processing customer with id=6 processing customer with id=20 processing customer with id=24 processing customer with id=28 processing customer with id=29 processing customer with id=82 processing customer with id=96
从输出结果可以清楚的看到，最小的元素在队列的头部因而最先被取出。如果不实现comparator，在建立customerpriorityqueue时会抛出classcastexception。
exception in thread "main" java.lang.classcastexception: com.journaldev.collections.customer cannot be cast to java.lang.comparable at java.util.priorityqueue.siftupcomparable(priorityqueue.java:633) at java.util.priorityqueue.siftup(priorityqueue.java:629) at java.util.priorityqueue.offer(priorityqueue.java:329) at java.util.priorityqueue.add(priorityqueue.java:306) at com.journaldev.collections.priorityqueueexample.adddatatoqueue(priorityqueueexample.java:45) at com.journaldev.collections.priorityqueueexample.main(priorityqueueexample.java:25)