1. PriorityQueue
的概念
概念
PriorityQueue
是优先级队列,它是堆在 Java 中的具体实现类- 它首先实现了队列接口
Queue
区别
- 与
LinkedList
类似,它的队列长度也没有限制 - 与一般队列的区别是,它有优先级的概念,每个元素都有优先级,队头的元素永远都是优先级最高的
- 与
实现
PriorityQueue
内部是用堆实现的,堆物理上就是数组- 与
ArrayList
类似,PriorityQueue
同样使用动态数组 - 内部元素不是完全有序的,不过,逐个出队会得到有序的输出
结构
- 虽然名字叫优先级队列,但也可以将
PriorityQueue
看作一种比较通用的实现了堆的性质的数据结构 - 可以用
PriorityQueue
来解决适合用堆解决的问题
- 虽然名字叫优先级队列,但也可以将
2. PriorityQueue
的基本用法
PriorityQueue
有多个构造方法,部分构造方法如下1
2
3public PriorityQueue()
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
public PriorityQueue(Collection<? extends E> c)PriorityQueue
是用堆实现的,堆物理上就是数组- 与
ArrayList
类似,PriorityQueue
同样使用动态数组,根据元素个数动态扩展 initialCapacity
表示初始的数组大小,可以通过参数传入- 对于默认构造方法,
initialCapacity
使用默认值 11(ArrayList
默认 10,HashMap
默认 16) - 对于最后的构造方法,数组大小等于参数容器中的元素个数
- 与
与
TreeMap/TreeSet
类似,为了保持一定顺序,PriorityQueue
要求要么元素实现Comparable
接口,要么传递一个比较器Comparator
3. 下面代码的输出是
1 | Queue<Integer> pq = new PriorityQueue<> (); |
- 结果:
2 4 6 7 8 10 12 12 13 15 19 22 34
- 分析:与普通队列不同,输出是从小到大排序的。如果希望从大到小排序的话,传递一个逆序的
Comparator
。即将第一行代码替换为:Queue<Integer> pq = new PriorityQueue<> (11, Collections.reverseOrder());
4. 下面代码的输出是
1 | //模拟一个任务队列,定义一个内部类 Task 表示任务 |
结果
1
2
3处理任务:写代码,优先级:100
处理任务:写日记,优先级:20
处理任务:看电视,优先级:10
5. PriorityQueue
的内部组成
源码基于 Java 7
1
2
3
4private transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
private transient int modCount = 0;queue
就是实际存储元素的数组size
表示当前元素个数comparator
为比较器,可以为null
modCount
纪录修改次数
6. PriorityQueue
的特点是
Java 中堆的实现类
PriorityQueue
,它实现了队列接口Queue
,但按优先级出队,内部使用堆实现的,而堆物理又是数组存储的,所以本质上是动态数组。有如下特点- 实现了优先级队列,最先出队的总是优先级最高的,即排序中的第一个
- 优先级可以有相同的,内部元素不是完全有序的,如果遍历输出,除了第一个,其他没有特定顺序
查看头部元素的效率很高,为
O(1)
;入队、出队效率比较高,为O(log2(N))
,构建堆 heapify 的效率为O(N)
根据值查找和删除元素的效率比较低,为
O(N)