在Java中如何使用PriorityQueue实现优先队列_PriorityQueue操作指南

P粉602998670 2025-11-11 00:00:00 次阅读

PriorityQueue基于堆实现，默认最小堆，poll()返回最小值；通过Comparator可实现最大堆或自定义排序，常用于任务调度、Dijkstra等场景。

在Java中，PriorityQueue 是实现优先队列最常用的方式。它基于堆（heap）数据结构，默认使用最小堆，也就是说队列头部的元素是队列中最小的。这意味着每次调用 poll() 或 peek() 方法时，都会返回当前优先级最高的元素（数值最小或自定义排序中最靠前的）。

PriorityQueue的基本特性

PriorityQueue 是 java.util 包中的一个类，实现了 Queue 接口。它具有以下关键特点：

不支持 null 元素（会抛出 NullPointerException）
不是线程安全的（多线程环境下需使用 PriorityBlockingQueue）
不允许插入不可比较的对象（除非提供 Comparator）
插入和删除操作的时间复杂度为 O(log n)，获取队首为 O(1)

默认最小堆的使用方法

当存储基本包装类型如 Integer、String 时，PriorityQueue 默认按自然顺序排列，即最小值优先。

PriorityQueue pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 输出 1
System.out.println(pq.poll()); // 输出 3
System.out.println(pq.poll()); // 输出 5

上面代码中，虽然插入顺序是 5、1、3，但出队顺序是 1、3、5，体现了“最小优先”原则。

使用Comparator实现最大堆或自定义排序

如果需要最大堆，或者对复杂对象排序，可以通过传入 Comparator 来实现。

创建最大堆：

PriorityQueue maxPQ = new PriorityQueue<>((a, b) -> b - a);
// 或使用 Collections.reverseOrder()
// PriorityQueue maxPQ = new PriorityQueue<>(Collections.reverseOrder());
maxPQ.offer(5);
maxPQ.offer(1);
maxPQ.offer(3);
System.out.println(maxPQ.poll()); // 输出 5
System.out.println(maxPQ.poll()); // 输出 3
System.out.println(maxPQ.poll()); // 输出 1

对自定义对象排序：

class Task {
    String name;
    int priority;
    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
}
PriorityQueue taskQueue = new PriorityQueue<>(
(t1, t2) -> t1.priority - t2.priority  // 优先级数字越小，优先级越高
);
taskQueue.offer(new Task("Low", 3));
taskQueue.offer(new Task("High", 1));
taskQueue.offer(new Task("Medium", 2));
System.out.println(taskQueue.poll().name); // 输出 "High"