编辑“︁Java PriorityQueue”︁

{{Note|本文适用于Java初学者及需要系统了解PriorityQueue的程序员。内容包含基础操作、源码分析及实际应用案例。}}

= Java PriorityQueue =

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

== 核心特性 ==
* '''非线程安全'''：多线程环境下需使用{{code|java.util.concurrent.PriorityBlockingQueue}}
* '''动态扩容'''：初始容量11，按需增长
* '''时间复杂度'''：
** 插入（offer）：<math>O(\log n)</math>
** 取出头部（poll/peek）：<math>O(\log n)</math>/<math>O(1)</math>
* '''不允许null元素'''：抛出{{code|NullPointerException}}

<mermaid>
graph TD
    A[PriorityQueue] --> B[AbstractQueue]
    B --> C[Queue]
    A --> D[Serializable]
    style A fill:#f9f,stroke:#333
</mermaid>

== 基础操作 ==
=== 初始化 ===
<syntaxhighlight lang="java">
// 自然排序（元素需实现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);
</syntaxhighlight>

=== 常用方法示例 ===
<syntaxhighlight lang="java">
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
</syntaxhighlight>

== 底层实现原理 ==
使用'''二叉小顶堆'''（最小堆）存储，数组结构如下：

<mermaid>
graph TD
    0((1)) --> 1((3))
    0 --> 2((5))
    1 --> 3((8))
    1 --> 4((6))
</mermaid>

对应数组表示：<code>[1, 3, 5, 8, 6]</code>

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

== 高级应用案例 ==
=== 医院急诊分诊系统 ===
<syntaxhighlight lang="java">
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);
}
</syntaxhighlight>

=== 合并K个有序链表 ===
<syntaxhighlight lang="java">
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;
</syntaxhighlight>

== 性能优化建议 ==
1. '''预分配容量'''：避免频繁扩容，构造函数指定初始大小
2. '''复杂对象排序'''：优先使用Comparator而非实现Comparable
3. '''批量操作'''：{{code|addAll}}比循环{{code|offer}}更高效

== 常见问题 ==
=== Q1: 如何实现大顶堆？ ===
<syntaxhighlight lang="java">
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Collections.reverseOrder()
    // 或 (a, b) -> b - a
);
</syntaxhighlight>

=== Q2: 为什么迭代顺序与优先级顺序不一致？ ===
迭代时调用{{code|iterator()}}返回的是堆的物理存储顺序，要按优先级顺序需循环调用{{code|poll()}}。

{{Warning|PriorityQueue的迭代器不保证按优先级顺序遍历}}

== 扩展阅读 ==
* 对比{{code|TreeSet}}：两者均可排序，但PriorityQueue允许重复元素
* 线程安全替代方案：{{code|PriorityBlockingQueue}}
* JDK源码分析：{{code|siftUp}}/{{code|siftDown}}方法的实现细节

[[Category:Java集合框架]]
[[Category:数据结构]]
[[Category:Java编程]]

[[Category:编程语言]]
[[Category:Java]]