Java PriorityQueue(优先队列)

2024-04-07后端4 分钟147 次阅读
AI 摘要salmon-ai

本文详细解析了 Java PriorityQueue 优先队列的核心概念、常用特性与典型用法,说明它与普通 FIFO 队列的区别,介绍了默认按自然顺序或比较器排序的规则,

前言

最近在做算法题时,会经常用到队列,而最近在学 dijkstra 算法时,就需要使用到优先队列,找到权值最小的边来处理。而 PriorityQueue 刚好可以满足需求。

1、简介

Java PriorityQueue 类是一种队列数据结构实现,其中根据优先级处理对象。它与遵循FIFO(先进先出)算法的标准队列不同。

在优先级队列中,添加的对象根据其优先级。默认情况下,优先级由对象的自然顺序决定。队列构建时提供的比较器可以覆盖默认优先级。

2、功能

  • PriorityQueue 是一个无限制的队列,并且动态增长。默认初始容量 11,我们可以使可以自定义容量的构造函数对其 initialCapacity 参数覆盖。
  • 它不允许NULL对象。
  • 添加到 PriorityQueue 的对象必须具有可比性(实现Comparable接口)。
  • 默认情况下,优先级队列的对象按自然顺序排序。
  • 比较器可用于队列中对象的自定义排序。
  • 优先级队列的头部是基于自然排序或基于比较器的排序的最小元素。当我们轮询队列时,它从队列中返回头对象。
  • 如果存在多个具有相同优先级的对象,则它可以随机轮询其中任何一个。
  • PriorityQueue 不是线程安全的。PriorityBlockingQueue 在并发环境中使用。
  • 它为 add 和 poll 方法提供了 O(log⁡n)O(\log n) 时间。

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 条
登录 之后才能评论
—
还没有评论,来说第一句