优先队列PriorityQueue详解

什么是优先队列?

优先队列(Priority Queue)是一种数据结构,它类似于队列,但每个元素都有一个权重。插入元素时按照权重的大小插入,取出元素时总是取出权重最大的元素。

Collection - PriorityQueue源码解析 图片来源:pdai
Collection - PriorityQueue源码解析 图片来源:pdai

常见的实现方式

优先队列有多种实现方式,其中最常见的两种是堆(Heap)和二叉搜索树(Binary Search Tree)。

实现方式 插入元素的时间复杂度 取出元素的时间复杂度 是否可动态修改元素的权重 是否支持随机访问
O(log n) O(1) 不支持 不支持
二叉搜索树 O(log n) O(log n) 支持 支持

Java中的实现:PriorityQueue

Java中的PriorityQueue实现了堆的数据结构,它是一种基于优先级的无界队列。此队列规定越“重要”的元素越靠近队首,当队列为空时,取出操作会返回null。

常见操作

方法 说明 时间复杂度
add() 插入元素 O(log n)
remove() 取出并删除队首元素 O(log n)
peek() 查看队首元素 O(1)
size() 获取队列大小 O(1)
isEmpty() 判断队列是否为空 O(1)

示例代码

PriorityQueue pq = new PriorityQueue<>();
pq.add(3);
pq.add(1);
pq.add(4);
pq.add(2);
while (!pq.isEmpty()) {
System.out.println(pq.remove());
}

输出为:

1
2
3
4

优先队列PriorityQueue详解

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注