Java Academy · 课时

使用 PriorityQueue 进行有序处理

在任务调度场景中，结合自然排序和自定义比较器使用 PriorityQueue

使用 PriorityQueue 进行有序处理 是 CoddyKit 上的免费 Java Academy 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

什么是 PriorityQueue？

PriorityQueue 默认是一个最小堆：自然顺序最小的元素始终位于队首。元素在内部并未排序——只有最小元素能保证位于前端。

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

内部堆结构

PriorityQueue 使用存储在数组中的二叉最小堆。索引为 i 的父节点始终小于或等于索引为 2i+1 和 2i+2 的子节点。这保证了 offer 和 poll 的复杂度为 O(log n)，peek 的复杂度为 O(1)。

使用反向 Comparator 的最大堆

要创建最大堆（最大元素优先），请传入 Comparator.reverseOrder()：

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

使用自定义对象的 PriorityQueue

请使用 Comparator 为自定义记录或类排序：

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Peek 与 Poll

peek() 返回队首元素但不会将其移除。poll() 会移除并返回该元素。队列为空时，两者都会返回 null（不同于会抛出异常的 element()/remove()）。

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

任务调度示例

PriorityQueue 非常适合用于 CPU 调度模拟，其中任务具有不同的优先级：

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

K 个最小元素

PriorityQueue 是一种经典工具，可以在不完全排序数组的情况下找出 K 个最小元素：

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

使用最大堆查找 K 个最大元素

另一种方法是在遍历过程中维护一个大小为 K 的最小堆，以找出 K 个最大元素：

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Dijkstra 算法模式

迪杰斯特拉最短路径算法依靠最小堆，始终先扩展代价最低的未访问节点：

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

遍历顺序无序

遍历 PriorityQueue 时，NOT 会按优先级顺序返回元素——只有 poll() 才会按优先级返回元素。若要获得排序后的输出，请反复调用 poll()，而不要使用增强 for 循环。

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

性能总结

PriorityQueue 的操作复杂度：

offer(e)：O(log n)
poll()：O(log n)
peek()：O(1)
contains(e)：O(n)
remove(e)：O(n)

它不是线程安全的。对于并发访问，请使用 PriorityBlockingQueue。

快速检查

使用增强 for 循环遍历 PriorityQueue 时，能保证元素具有什么顺序？

回顾：PriorityQueue

要点：

PriorityQueue 是最小堆：最小元素会最先被 poll
使用 Comparator.reverseOrder() 创建最大堆
offer 和 poll 的复杂度为 O(log n)，peek 的复杂度为 O(1)
经典使用场景：第 K 大或第 K 小元素、迪杰斯特拉算法、任务调度
增强 for 循环不会提供优先级顺序——请使用 poll()

常见问题解答

「使用 PriorityQueue 进行有序处理」课时是免费的吗？

是的 — 「使用 PriorityQueue 进行有序处理」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「使用 PriorityQueue 进行有序处理」这节课中我会学到什么？

在任务调度场景中，结合自然排序和自定义比较器使用 PriorityQueue 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「使用 PriorityQueue 进行有序处理」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Java Academy