Java PriorityQueue(优先队列)
AI 摘要salmon-ai
本文详细解析了 Java PriorityQueue 优先队列的核心概念、常用特性与典型用法,说明它与普通 FIFO 队列的区别,介绍了默认按自然顺序或比较器排序的规则,
前言
最近在做算法题时,会经常用到队列,而最近在学 dijkstra 算法时,就需要使用到优先队列,找到权值最小的边来处理。而 PriorityQueue 刚好可以满足需求。
1、简介
Java PriorityQueue 类是一种队列数据结构实现,其中根据优先级处理对象。它与遵循FIFO(先进先出)算法的标准队列不同。
在优先级队列中,添加的对象根据其优先级。默认情况下,优先级由对象的自然顺序决定。队列构建时提供的比较器可以覆盖默认优先级。
2、功能
- PriorityQueue 是一个无限制的队列,并且动态增长。默认初始容量 11,我们可以使可以自定义容量的构造函数对其 initialCapacity 参数覆盖。
- 它不允许NULL对象。
- 添加到 PriorityQueue 的对象必须具有可比性(实现Comparable接口)。
- 默认情况下,优先级队列的对象按自然顺序排序。
- 比较器可用于队列中对象的自定义排序。
- 优先级队列的头部是基于自然排序或基于比较器的排序的最小元素。当我们轮询队列时,它从队列中返回头对象。
- 如果存在多个具有相同优先级的对象,则它可以随机轮询其中任何一个。
PriorityQueue不是线程安全的。PriorityBlockingQueue在并发环境中使用。- 它为 add 和 poll 方法提供了 时间。
3、示例
下边我就用实现迪杰斯特拉算法时,使用优先队列来选择最小权值边的代码来演示下。
主要在待处理节点那块,使用优先队列,找到从起点出发时,权值最小的那个节点,进行优先处理。
java
import java.io.*;
import java.util.*;
public class Main {
// 边
private static class Edge {
int from, to;
long w;
Edge(int a, int b, long w) {
this.from = a;
this.to = b;
this.w = w;
}
}
// 用于优先队列,优先选取从权值和最小的结点作为中转节点
private static class SNode implements Comparable<SNode> {
int id; // 结点编号
long n_dis; // 存储从起点到该结点的最短权值和
SNode(int id, long n_dis) {
this.id = id;
this.n_dis = n_dis;
}
@Override
public int compareTo(SNode o) {
return Long.compare(this.n_dis, o.n_dis);
}
}
static int N = 300005;
static long INF = 0x3f3f3f3f3f3f3f3fL;
// 存储从 1 ~ n 的邻接边
static ArrayList<Edge>[] e = new ArrayList[N];
static int n, m;
static int[] pre = new int[N]; // 存储编号的前驱节点
static long[] dis = new long[N]; // 存储 1 到 每个节点的最短路径值
static boolean[] vistied = new boolean[N]; // 标记是否访问过
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
for (int i = 1; i <= n; i++)
e[i] = new ArrayList<>();
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
long w = Long.parseLong(st.nextToken());
e[u].add(new Edge(u, v, w));
}
dijkstra(1);
for (int i = 1; i <= n; i++) {
if (dis[i] >= INF) {
System.out.print("-1 ");
} else {
System.out.print(dis[i] + " ");
}
}
}
/**
* 迪杰斯特拉
*
* @param start 起点编号
*/
private static void dijkstra(int start) {
// 初始化 1 到 每个点的权值无穷大
Arrays.fill(dis, INF);
dis[start] = 0; // 起点到自己本身是0
// 存储待处理的节点
// 注意,该队列是按照我们比较器的顺序来取出元素的。
PriorityQueue<SNode> queue = new PriorityQueue<>();
// 将起点加入待处理
queue.add(new SNode(start, dis[start]));
while (!queue.isEmpty()) {
SNode node = queue.poll();
// 查看该节点是否处理过
if (vistied[node.id])
continue;
vistied[node.id] = true;
// 访问其邻接节点
for (Edge edge : e[node.id]) {
// 访问未被处理过的邻接节点
if (vistied[edge.to]) {
continue;
}
// 计算从起点经过 node 到达 edge 的权值,看看是否比原来的更好
dis[edge.to] = Math.min(dis[edge.to], node.n_dis + edge.w);
// 添加到待处理队列
queue.add(new SNode(edge.to, dis[edge.to]));
pre[edge.to] = node.id; // 记录前驱节点,用于溯源
}
}
}
}
4、构造函数
- PriorityQueue():使用默认初始容量 11 构造空队列,该容量根据其自然顺序对其元素进行排序。
- PriorityQueue(Collection c):构造包含指定集合中元素的空队列。
- PriorityQueue(int initialCapacity):构造具有指定初始容量的空队列,该容量根据其自然顺序对其元素进行排序。
- PriorityQueue(int initialCapacity,Comparator comparator):构造具有指定初始容量的空队列,该容量根据指定的比较器对其元素进行排序。
- PriorityQueue(PriorityQueue c):构造包含指定优先级队列中元素的空队列。
- PriorityQueue(SortedSet c):构造包含指定有序集合中元素的空队列。
5、常用方法
- boolean add(object):将指定的元素插入此优先级队列。
- boolean offer(object):将指定的元素插入此优先级队列。
- boolean remove(object):从此队列中删除指定元素的单个实例(如果存在)。
- Object poll():检索并删除此队列的头部,如果此队列为空,则返回null。
- Object element():检索但不删除此队列的头部,如果此队列为空,则返回null。
- Object peek():检索但不删除此队列的头部,如果此队列为空,则返回null。
- void clear():从此优先级队列中删除所有元素。
- Comparator comparator():返回用于对此队列中的元素进行排序的比较器,如果此队列根据其元素的自然顺序排序,则返回null。
- boolean contains(Object o):如果此队列包含指定的元素,则返回true。
- Iterator iterator():返回此队列中元素的迭代器。
- int size():返回此队列中的元素数。
- Object [] toArray():返回包含此队列中所有元素的数组。
评论
0 条—
还没有评论,来说第一句