0%

Java 堆与优先级队列(二):剖析 PriorityQueue

1. PriorityQueue 的概念

  • 概念

    • PriorityQueue 是优先级队列,它是堆在 Java 中的具体实现类
    • 它首先实现了队列接口 Queue
  • 区别

    • LinkedList 类似,它的队列长度也没有限制
    • 与一般队列的区别是,它有优先级的概念,每个元素都有优先级,队头的元素永远都是优先级最高的
  • 实现

    • PriorityQueue 内部是用堆实现的,堆物理上就是数组
    • ArrayList 类似,PriorityQueue 同样使用动态数组
    • 内部元素不是完全有序的,不过,逐个出队会得到有序的输出
  • 结构

    • 虽然名字叫优先级队列,但也可以将 PriorityQueue 看作一种比较通用的实现了堆的性质的数据结构
    • 可以用 PriorityQueue 来解决适合用堆解决的问题

2. PriorityQueue 的基本用法

  • PriorityQueue 有多个构造方法,部分构造方法如下

    1
    2
    3
    public 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
2
3
4
5
6
7
Queue<Integer> pq = new PriorityQueue<> ();
pq.offer(10); //在尾部添加元素,队列满时返回 false
pq.add(22); //在尾部添加元素,队列满时抛异常
pq.addAll(Arrays.asList(new Integer[] {11, 12, 34, 2, 7, 4, 15, 12, 8, 6, 19, 13}));
while(pq.peek() != null) {
System.out.print(pq.poll() + " "); //E poll() --> 删除头部元素并返回,队列空时返回 null
}
  • 结果:2 4 6 7 8 10 12 12 13 15 19 22 34
  • 分析:与普通队列不同,输出是从小到大排序的。如果希望从大到小排序的话,传递一个逆序的 Comparator。即将第一行代码替换为:Queue<Integer> pq = new PriorityQueue<> (11, Collections.reverseOrder());

4. 下面代码的输出是

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
//模拟一个任务队列,定义一个内部类 Task 表示任务
static class Task {
int priority; //优先级,值越大优先级越高
String name; //任务名称
//省略构造方法和 getter 方法
}

//Task 没有实现 Comparable,这里定义一个单独的静态成员 taskComparator 表示比较器
private static Comparator<Task> taskComparator = new Comparator<Task> () {
@Override
public int compare(Task o1, Task o2) {
if(o1.getPriority() > o2.getPriority()) {
return -1;
} else if(o1.getPriority() < o2.getPriority()) {
return 1;
}
return 0;
}
}

Queue<Task> tasks = new PriorityQueue<Task> (11, taskComparator);
tasks.offer(new Task(20, "写日记"));
tasks.offer(new Task(10, "看电视"));
tasks.offer(new Task(100, "写代码"));
Task task = tasks.poll();
while(task != null) {
System.out.print("处理任务:" + task.getName() + ", 优先级: " + task.getPriority() + "\n");
task = tasks.poll();
}
  • 结果

    1
    2
    3
    处理任务:写代码,优先级:100
    处理任务:写日记,优先级:20
    处理任务:看电视,优先级:10

5. PriorityQueue 的内部组成

  • 源码基于 Java 7

    1
    2
    3
    4
    private 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)

-------------------- 本文结束感谢您的阅读 --------------------