当前位置：首页 > news >正文

java基础-PriorityQueue（优先队列）

news 2026/6/16 23:49:46

1. 基本概念

PriorityQueue 是 Java 集合框架中的一个基于优先堆的无界队列。它使用优先顺序（通常是元素的自然顺序或自定义比较器）来管理元素，而不是标准的 FIFO（先进先出）顺序。

// 基本创建方式 PriorityQueue<Integer> pq = new PriorityQueue<>(); // 最小堆（默认） PriorityQueue<Integer> pqMax = new PriorityQueue<>(Collections.reverseOrder()); // 最大堆

2. 核心特性

特性	说明
排序方式	元素按优先级排序，队头总是优先级最高的元素
数据结构	基于二叉堆实现（默认最小堆）
线程安全	❌不是线程安全的（如需线程安全用`PriorityBlockingQueue`）
null元素	❌ 不允许插入 null
时间复杂度	插入/删除：O(log n)，获取队头：O(1)

3. 常用操作示例

import java.util.PriorityQueue; public class PriorityQueueDemo { public static void main(String[] args) { // 1. 创建最小堆（默认） PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 添加元素 minHeap.offer(5); minHeap.offer(1); minHeap.offer(3); minHeap.offer(2); System.out.println("最小堆元素顺序："); while (!minHeap.isEmpty()) { System.out.print(minHeap.poll() + " "); // 输出: 1 2 3 5 } // 2. 创建最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 自定义比较器 maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3); System.out.println("\n最大堆元素顺序："); while (!maxHeap.isEmpty()) { System.out.print(maxHeap.poll() + " "); // 输出: 5 3 1 } // 3. 自定义对象排序 PriorityQueue<Student> studentQueue = new PriorityQueue<>( (s1, s2) -> s1.score - s2.score // 按分数升序 ); } } class Student { String name; int score; // 构造方法等... }

4. 底层实现原理

// 简化版内部结构理解 public class PriorityQueue<E> { private Object[] queue; // 存储元素的数组（二叉堆） private Comparator<? super E> comparator; // 添加元素时的上浮操作（heapify-up） // 删除元素时的下沉操作（heapify-down） }

默认最小堆：父节点 ≤ 子节点
存储结构：数组实现的完全二叉树
父子节点关系：
- 父节点索引：(i-1)/2
- 左子节点：2*i + 1
- 右子节点：2*i + 2

5. 典型应用场景

// 场景1：Top K 问题（找出最大的K个元素） public List<Integer> topK(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); // 移除最小的，保持K个最大的 } } return new ArrayList<>(minHeap); } // 场景2：合并多个有序列表 public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>( (a, b) -> a.val - b.val ); // 将每个链表的头节点加入队列 // 每次弹出最小的，加入其下一个节点 } // 场景3：任务调度（按优先级执行） PriorityQueue<Task> taskQueue = new PriorityQueue<>( Comparator.comparingInt(Task::getPriority) );

6. 注意事项

// ⚠️ 注意1：遍历时不保证顺序 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(3); pq.add(1); pq.add(2); System.out.println(pq); // 可能输出 [1, 3, 2] // 只有 poll() 或 peek() 才能看到正确顺序 // ⚠️ 注意2：不能插入不可比较对象 // PriorityQueue<Object> pq = new PriorityQueue<>(); // pq.add(new Object()); // 运行时错误：ClassCastException // ✅ 解决方案：提供Comparator PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>( Map.Entry.comparingByValue() );

7. 与相关类的比较

类	排序方式	线程安全	边界
`PriorityQueue`	优先级顺序	❌ 不安全	无界
`ArrayDeque`	FIFO/LIFO	❌ 不安全	无界
`LinkedList`	插入顺序	❌ 不安全	无界
`PriorityBlockingQueue`	优先级顺序	✅ 安全	无界