# PriorityQueue简介

# 一、总体概述

java.util.PriorityQueue<E> 基于最小堆 实现的可伸缩队列，符合队列 FIFO 的“取元素”语义，但优先级由比较器决定。它实现 Queue<E>、Serializable，默认小顶堆（最小值最高优先），可通过自定义 Comparator 变为最大堆或任意优先策略。

# 二、底层实现原理

维度	说明
核心结构	二叉堆：用 `Object[] queue` 存储，根节点索引 0，`i` 的左右孩子为 `2i+1 / 2i+2`
比较逻辑	- 若构造时传入 `Comparator<? super E>`，永远用它比较 - 否则要求 `E` 实现 `Comparable<E>`，按自然顺序
动态扩容	初始容量默认 11；插入时若满 → `Arrays.copyOf` 扩成 `old + (old < 64 ? old + 2 : old >> 1)`
堆调节	- 上浮：`siftUp()` —— 新元素插入末尾，沿父方向与更小者交换 - 下沉：`siftDown()` —— 弹出堆顶后把最后一个元素放根，自顶向下与更小孩子交换
稳定性	不保证稳定；相等优先级元素的顺序可能变化

# 三、复杂度分析

操作	时间复杂度	备注
`offer/add`	O(log n)	上浮
`poll/remove()`	O(log n)	下沉
`peek`	O(1)	直接读根
`contains / remove(Object)`	O(n)	线性扫描
迭代	O(n)	非堆序（不可排序遍历）
空间	O(n)	数组持有全部元素

常数因子：比 TreeSet/TreeMap 更低（无额外指针、旋转），因此在仅需堆顶最值时更快。

# 四、完整 API 速查

分类	常用方法	说明
构造	`PriorityQueue()` / `PriorityQueue(int cap)`	默认小顶堆
	`PriorityQueue(Comparator)`	自定义优先级
	`PriorityQueue(Collection<? extends E>)`	线性堆化 O(n)
插入	`boolean add(E)`（抛异常） `boolean offer(E)`（返回 false）	放入元素
访问	`E peek()`	查看堆顶，不删除
弹出	`E poll()` / `E remove()`	删除并返回堆顶 `remove(Object)` 删除任意元素
批量	`addAll(Collection)` / `clear()`
属性	`size()` / `isEmpty()`
遍历	`Iterator<E>`	任意顺序，Fail‑fast
数组化	`toArray()` / `toArray(T[])`

# 五、注意事项 & 易错点

⚠️ 点	细节
`null` 禁止	插入 `null` 抛 `NullPointerException`（优先级无法比较）
迭代顺序	`iterator()` 不是优先级顺；仅保证包含全部元素
相等元素	允许重复；比较器返回 0 则视为同优先级，不会去重
修改元素字段	若元素的 `compareTo/compare` 结果在队列中被修改 ⇒ 堆顺序被破坏，应移除‑修改‑重插
contains/remove(Object)	内部线性查找，`O(n)`，大量调用需谨慎
容量扩容	自动扩容但可能多次 `System.arraycopy`，若已知规模可预设容量
线程安全	非线程安全：多线程并发写需外部同步；在并发场景用 `PriorityBlockingQueue`（无界）或自己加锁

# 六、典型使用场景

场景	说明
最短路径 Dijkstra / A*	`int[] {node, dist}` 或自定义 Node，最小堆按距离
K 个有序数组归并	堆存每个数组当前头元素，弹出后推新元素
Top‑K	维护大小 K 的“最大堆”或“最小堆”
流式中位数	双堆：大顶堆 + 小顶堆
任务调度	根据时间戳 / 权重弹出下一个任务
多路归并排序	外排、磁盘归并

# 七、线程安全方案

方案	说明
`Collections.synchronizedCollection(pq)`	简单互斥包装，粒度大
`PriorityBlockingQueue`	JDK 并发包，基于无锁堆 + ReentrantLock 适用生产消费者
手动锁	`ReentrantLock` / `synchronized` 包围关键操作

# 八、性能细节

批量构造更快：new PriorityQueue<>(collection) 采用 Floyd 堆化，O(n)；逐个 add 为 O(n log n)。
最大堆技巧：PriorityQueue<Integer> max = new PriorityQueue<>((a,b)->b-a);。
数组缓存：JDK 17 开始 siftUp / siftDown 内联优化，实测百万级插入 ≈ 7–10 M ops/s（取决于对象大小）。
小顶堆变 K 小：当只关心 Top‑K 最大元素时，用 固定容量最小堆，当大小>k 时 poll()。

# 九、示例代码

import java.util.*;

public class PriorityQueueDemo {

    // Top K 最大元素
    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // 小顶堆
        for (int n : nums) {
            if (minHeap.size() < k) minHeap.offer(n);
            else if (n > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(n);
            }
        }
        return new ArrayList<>(minHeap); // 未排序
    }

    // Dijkstra
    static int dijkstra(int n, List<int[]>[] g, int src, int dst) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0], d = cur[1];
            if (u == dst) return d;
            if (d > dist[u]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // Top‑K
        System.out.println(topK(new int[]{5, 2, 9, 1, 7, 6}, 3)); // [6,7,9]

        // 最大堆示例
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->b-a);
        maxHeap.addAll(Arrays.asList(4, 1, 7));
        System.out.println(maxHeap.poll()); // 7
    }
}

# 🔚 小结

PriorityQueue = 最小（或自定义）堆 + 动态数组；
提供 O(log n) 的入队/出队，O(1) 查看堆顶；
适用于 Top‑K、Dijkstra、K 路归并、流式统计 等；
非线程安全，并发场景选 PriorityBlockingQueue 或外部加锁；
避免迭代器顺序误解、避免修改元素优先级后不重平衡、合理设置初始容量。

← 图说Stream中的skip()和limit()方法及组合使用 TreeMap简介 →