一、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源码分析
成员：
|
1
2
|
priavte transient Object[] queue;private int size = 0; |
1.PriorityQueue构造小顶堆的过程
这里我们以priorityQueue构造器传入一个容器为参数PriorityQueue(Collecntion<? extends E>的例子：
构造小顶堆的过程大体分两步：
复制容器数据，检查容器数据是否为null
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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这个节点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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的节点：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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;} |
总体的建立小顶堆的过程就是：
|
1
2
3
4
|
private void initFromCollection(Collection<? extends E> c) { initElementsFromCollection(c); heapify(); } |
其中heapify就是siftDown的过程。
2.PriorityQueue容量扩容过程
从实例成员可以看出，PriorityQueue维护了一个Object[], 因此它的扩容方式跟顺序表ArrayList相差不多。
这里只给出grow方法的源码
|
1
2
3
4
5
6
7
8
9
10
11
|
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 的小顶堆。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
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的比较器。
当我运行以上测试程序时，我得到以下输出：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
Processing Integer:9Processing Integer:16Processing Integer:18Processing Integer:25Processing Integer:33Processing Integer:75Processing Integer:77Processing Customer with ID=6Processing Customer with ID=20Processing Customer with ID=24Processing Customer with ID=28Processing Customer with ID=29Processing Customer with ID=82Processing Customer with ID=96 |
从输出结果可以清楚的看到，最小的元素在队列的头部因而最先被取出。如果不实现Comparator，在建立customerPriorityQueue时会抛出ClassCastException。
|
1
2
3
4
5
6
7
|
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) |
