PriorityQueue是队列结构的一种，是0个或0个以上元素的集合，每个元素都有优先级。优先级队列内置于JDK中。本文分析了Java中优先级队列结构的源代码和用法。
一、PriorityQueue的数据结构
JDK7中PriorityQueue的数据结构是二进制堆。准确地说，是最小堆。
二叉堆是一种特殊的堆，类似于完全二叉树。二叉堆满足特征：父节点的键值始终与任意子节点的键值保持固定的顺序关系，每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何子节点的键值时，就是最大堆。当父节点的键值总是小于或等于任何子节点的键值时，就是最小堆。
下图是最大的堆。
priorityQueue的队列头是给定顺序中最小的元素。
PriorityQueue不允许空值，并且不支持不可比较的对象。PriorityQueue要求使用Compare和Comparator接口对对象进行排序，排序时会根据优先级处理其中的元素。
priorityQueue的大小没有限制，但是初始大小可以在创建时指定。当添加队列元素时，队列将自动扩展。
PriorityQueue不是线程安全的，类似的PriorityBlockingQueue是线程安全的。
我们知道队列遵循先进先出的模式，但是有时需要根据优先级处理队列中的对象。例如，假设我们有一个应用程序，它在每天的交易时间内生成股票报告，需要处理大量的数据，需要大量的处理时间。当客户向这个应用程序发送请求时，它实际上进入了队列。我们需要首先处理优先客户，然后是普通用户。在这种情况下，Java的PriorityQueue会很有帮助。
PriorityQueue是一个基于优先级堆的无限队列。默认情况下，这个优先级队列中的元素可以自然排序，或者在实例化队列时由提供的比较器排序。
优先级队列不允许空值，也不支持不可比的对象，比如用户定义的类。优先级队列要求使用Java Comparable和Comparator接口对对象进行排序，排序时会根据优先级处理其中的元素。
优先级队列的头是基于自然排序或比较排序的最小元素。如果有多个相同排序的对象，可以随机选择其中的任何一个。当我们得到队列时，我们返回队列的头对象。
优先级队列的大小没有限制，但是初始大小可以在创建时指定。当我们向优先级队列添加元素时，队列大小将自动增加。
PriorityQueue是非线程安全的，所以Java为Java多线程环境提供了PriorityBlockingQueue(实现BlockingQueue接口)。
二、PriorityQueue源码分析
成员：
priavte临时对象[]队列；
private int size=0；
1.PriorityQueue构造小顶堆的过程
这里我们取priorityQueue构造函数传入的一个容器作为参数PriorityQueue (college？延伸E的示例：
构建小顶桩的过程大致分为两个步骤：
复制容器数据并检查容器数据是否为空。
私有void initElementsFromCollection(集合？扩展E c) {
object[]a=c . to array()；
//如果c.toArray错误地没有返回Object[]，就复制它。
if (a.getClass()！=对象[]。类)
a=Arrays.copyOf(a，a.length，Object[]。类)；
int len=a.length
if (len==1 || this.comparator！=空)
for(int I=0；我len我)
if (a[i]==null)
抛出新的NullPointerException()；
this . queue=a；
this . size=a . length；
}
调整数据以满足小顶桩的结构。
首先介绍了siftUp和siftDown两种调整方法。
SiftDown:当给定一个初始化元素时，应该调整该元素以满足最小堆的结构属性。因此，从上到下不断地比较和交换元素X与子节点的键值，直到你发现元素X的键值小于或等于子节点的键值(也就是确保它小于它的左右节点)，或者下降到叶子节点。
例如如下的示意图，调整9这个节点：
私有void向下筛选comparable(int k，E x) {
可比？超E键=(可比？超e)x；
int half=size 1；//size/2是第一个叶子结点的下标
//只要没到叶子节点
while (k half) {
int child=(k 1)1；//左孩子
object c=queue[child]；
int right=child 1；
//找出左右孩子中小的那个
如果（大小合适
((可比？超级E) c).compareTo((E) queue[right]) 0)
c=队列[子=右]；
if (key.compareTo((E) c)=0)
打破；
queue[k]=c；
k=孩子；
}
queue[k]=key；
}
siftUp:优先级队列每次新增加一个元素的时候是将新元素插入对尾的。因此，应该与siftDown有同样的调整过程，只不过是从下（叶子)往上调整。
例如如下的示意图，填加键为3的节点：
私有空siftup comparable(int k，E x) {
可比？超E键=(可比？超e)x；
while (k 0) {
int parent=(k-1)1；//获取父母下标
object e=queue[parent]；
if (key.compareTo((E) e)=0)
打破；
queue[k]=e；
k=父母；
}
queue[k]=key；
}
总体的建立小顶堆的过程就是：
私有void initFromCollection(集合？扩展中文){
initElementsFromCollection(c)；
heap ify()；
}
其中使肥胖就是siftDown的过程。
2.PriorityQueue容量扩容过程
从实例成员可以看出，优先级队列维护了一个对象[],因此它的扩容方式跟顺序表数组列表相差不多。
这里只给出生长方法的源码
私有void grow(int minCapacity) {
int oldCapacity=queue.length
//小的话双倍大小；其他增长50%
int新容量=旧容量((旧容量64)？
（旧容量2):
（旧容量1));
//溢出感知代码
if (newCapacity - MAX_ARRAY_SIZE 0)
新增产能=巨大产能(最小产能)；
queue=Arrays.copyOf(queue，new capacity)；
}
可以看出，当数组的容量不大的时候，每次扩容也不大。当数组容量大于64的时候，每次扩容双倍。
三、PriorityQueue的应用
eg1:
这里给出一个最简单的应用：从动态数据中求第K个大的数。
思路就是维持一个大小=k的小顶堆。
//数据是动态数据
//堆维持动态数据的堆
//分辨率用来保存第K大的值
public boolean kthLargest(int data，int k，PriorityQueueInteger heap，int[] res) {
if(heap.size() k) {
heap.offer(数据);
if(heap.size()==k) {
RES[0]=堆。peek()；
返回真实的
}
返回错误的
}
if(heap.peek() data) {
堆。poll()；
heap.offer(数据);
}
RES[0]=堆。peek()；
返回真实的
}
eg2:
我们有一个用户类顾客，它没有提供任何类型的排序。当我们用它建立优先队列时，应该为其提供一个比较器对象。
Customer.java
包com。日志开发。收藏；
公共类客户{
私有int id
私有字符串名称；
公共客户(int i，String n){
这个。id=I；
这个。name=n；
}
public int getId() {
返回id；
}
公共字符串getName() {
返回名称；
}
}
我们使用Java 语言(一种计算机语言，尤用于创建网站)语言（一种计算机语言，尤用于创建网站)随机数生成随机用户对象。对于自然排序，我们使用整数对象，这也是一个封装过的Java 语言(一种计算机语言，尤用于创建网站)语言（一种计算机语言，尤用于创建网站)对象。
下面是最终的测试代码，展示如何使用优先级队列：
PriorityQueueExample.java
包com。日志开发。收藏；
导入Java。util。比较器；
导入Java。util。优先级队列；
导入Java。util。排队；
导入Java。util。随机；
public class PriorityQueueExample {
公共静态void main(String[] args) {
//优先队列自然排序示例
queue integerPriorityQueue=新优先级队列(7)；
Random rand=new Random()；
for(int I=0；i7；i ){
integerPriorityQueue.add(新整数(兰德。nextint(100)))；
}
for(int I=0；i7；i ){
整数in=integerpriorityqueue。poll()；
System.out.println('处理整数：' in ')；
}
//优先队列使用示例
queue customer customerporityqueue=新优先级队列(7，id比较器)；
addDataToQueue(customerPriorityQueue)；
pollDataFromQueue(customerPriorityQueue)；
}
//匿名比较仪实现
公共静态比较器客户id比较器=新比较器客户(){
@覆盖
公共（同Internationalorganizations）国际组织比较（客户c1，客户c2) {
return(int)(C1。getid()-C2。getid())；
}
};
//用于往队列增加数据的通用方法
私有静态void addDataToQueue(队列客户客户优先级队列){
Random rand=new Random()；
for(int I=0；i7；i ){
int id=rand。nextint(100)；
customerPriorityQueue.add(新客户(id，' Pankaj ' id))；
}
}
//用于从队列取数据的通用方法
私有静态void pollDataFromQueue(队列客户客户优先级队列){
while(true){
customer cust=customerporityqueue。poll()；
if(cust==null)break；
System.out.println('处理ID=' cust.getId()'的客户);
}
}
}
注意我用实现了比较仪接口的Java 语言(一种计算机语言，尤用于创建网站)语言（一种计算机语言，尤用于创建网站)匿名类，并且实现了基于身份证明(识别)的比较器。
当我运行以上测试程序时，我得到以下输出：
处理整数：9
处理整数：16
处理整数：18
处理整数：25
处理整数：33
处理整数：75
处理整数：77
正在处理ID=6的客户
正在处理ID=20的客户
正在处理ID=24的客户
正在处理ID=28的客户
正在处理ID=29的客户
处理ID=82的客户
处理ID=96的客户
从输出结果可以清楚的看到，最小的元素在队列的头部因而最先被取出。如果不实现比较器，在建立客户优先级队列时会抛出ClassCastException。
线程"主要"中出现异常Java。郎。classcastexception:com。日志开发。收藏。顾客不能转换为可比较的
位于Java。util。优先级队列。siftupcumbrable(优先级队列。Java:633)
位于Java。util。优先级队列。向上筛选(优先级队列。Java:629)
位于Java。util。优先级队列。报价(优先排队。Java:329)
位于Java。util。优先级队列。添加(优先级队列。Java:306)
位于com。日志开发。收藏。priorityqueueexample。adddatatoqueue(priorityqueueexample。Java:45)
位于com。日志开发。收藏。priorityqueueexample。main(priorityqueueexample。Java:25)
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。