Java PriorityQueue[编辑 | 编辑源代码]

PriorityQueue（优先级队列）是Java集合框架中基于堆实现的特殊队列，元素按照优先级顺序出队（默认自然排序或通过Comparator定制）。与普通队列（FIFO）不同，其出队顺序取决于优先级，是处理任务调度、贪心算法等场景的高效数据结构。

核心特性[编辑 | 编辑源代码]

非线程安全：多线程环境下需使用
```
java.util.concurrent.PriorityBlockingQueue
```
动态扩容：初始容量11，按需增长
时间复杂度：
- 插入（offer）： $O (\log n)$
- 取出头部（poll/peek）： $O (\log n)$ / $O (1)$
不允许null元素：抛出
```
NullPointerException
```

基础操作[编辑 | 编辑源代码]

初始化[编辑 | 编辑源代码]

// 自然排序（元素需实现Comparable）
PriorityQueue<Integer> naturalQueue = new PriorityQueue<>();

// 自定义Comparator
PriorityQueue<String> lengthQueue = new PriorityQueue<>(
    (a, b) -> a.length() - b.length()
);

// 初始化集合
List<Integer> nums = Arrays.asList(5, 3, 8);
PriorityQueue<Integer> fromCollection = new PriorityQueue<>(nums);

常用方法示例[编辑 | 编辑源代码]

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);  // 插入元素
pq.offer(1);
pq.offer(3);

System.out.println(pq.peek());  // 输出: 1（查看头部）
System.out.println(pq.poll());  // 输出: 1（移除头部）
System.out.println(pq.size());  // 输出: 2

底层实现原理[编辑 | 编辑源代码]

使用二叉小顶堆（最小堆）存储，数组结构如下：

对应数组表示：[1, 3, 5, 8, 6]

关键操作流程： 1. 插入：元素添加到末尾，然后"上浮"（siftUp） 2. 删除：头部与末尾交换，移除末尾，新头部"下沉"（siftDown）

高级应用案例[编辑 | 编辑源代码]

医院急诊分诊系统[编辑 | 编辑源代码]

class Patient implements Comparable<Patient> {
    String name;
    int severity; // 1-5级（5为最紧急）

    public int compareTo(Patient other) {
        return other.severity - this.severity; // 降序排列
    }
}

PriorityQueue<Patient> erQueue = new PriorityQueue<>();
erQueue.add(new Patient("Alice", 3));
erQueue.add(new Patient("Bob", 5)); // 最先处理
erQueue.add(new Patient("Charlie", 2));

while (!erQueue.isEmpty()) {
    System.out.println("正在治疗: " + erQueue.poll().name);
}

合并K个有序链表[编辑 | 编辑源代码]

PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
    (a, b) -> a.val - b.val
);

// 将所有链表头节点入队
lists.stream().filter(Objects::nonNull).forEach(minHeap::offer);

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!minHeap.isEmpty()) {
    tail.next = minHeap.poll();
    tail = tail.next;
    if (tail.next != null) {
        minHeap.offer(tail.next); // 将下一个节点入队
    }
}
return dummy.next;

性能优化建议[编辑 | 编辑源代码]

1. 预分配容量：避免频繁扩容，构造函数指定初始大小 2. 复杂对象排序：优先使用Comparator而非实现Comparable

3. 批量操作：

addAll

比循环

offer

更高效

常见问题[编辑 | 编辑源代码]

Q1: 如何实现大顶堆？[编辑 | 编辑源代码]

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Collections.reverseOrder()
    // 或 (a, b) -> b - a
);

Q2: 为什么迭代顺序与优先级顺序不一致？[编辑 | 编辑源代码]

迭代时调用

iterator()

返回的是堆的物理存储顺序，要按优先级顺序需循环调用

poll()

。 页面模块:Message box/ambox.css没有内容。

扩展阅读[编辑 | 编辑源代码]

对比
```
TreeSet
```
：两者均可排序，但PriorityQueue允许重复元素
线程安全替代方案：
```
PriorityBlockingQueue
```
JDK源码分析：
```
siftUp
```
/
```
siftDown
```
方法的实现细节