PriorityQueue 的底层原理是什么？出队顺序是怎样的？
简化版
PriorityQueue 是优先队列，出队顺序不是先进先出，而是按优先级——默认最小元素先出（小顶堆）。底层是一个用数组存储的二叉堆：入队 offer 把元素放到数组末尾再「上浮」到合适位置，出队 poll 取走堆顶（数组第 0 个）再把末尾元素放到堆顶「下沉」调整，两者都是 O(log n)，取堆顶 peek 是 O(1)。典型用途：Top K、任务按优先级调度、Dijkstra 最短路。
详细版
核心：数组实现的完全二叉堆。PriorityQueue 用 Object[] queue 存元素，逻辑上是一棵完全二叉树，但不用指针——靠下标算父子关系：
下标 i 的节点：
父节点 = (i - 1) / 2
左孩子 = 2i + 1
右孩子 = 2i + 2
小顶堆性质：每个节点 ≤ 它的两个孩子 → 堆顶（下标 0）永远是最小值offer(e)（入队，上浮 siftUp）：元素放到数组末尾（树的最后一个位置），然后不断和父节点比较，比父小就交换，直到不小于父或到根。O(log n)。
poll()（出队，下沉 siftDown）：取走堆顶（最小值），把数组最后一个元素移到堆顶，然后不断和较小的孩子比较、交换下沉，恢复堆性质。O(log n)。
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 默认小顶堆
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll(); // 1（最小先出，不是先进的 5）
pq.peek(); // 3（此时堆顶）
// 大顶堆：传 Comparator 反转
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());⚠️ PriorityQueue 只保证堆顶是最小/最大，数组里其余元素并非完全有序。直接遍历（for-each / toArray）得到的顺序不是排序结果；要有序只能反复 poll。
完整版教学
一、为什么需要「优先队列」这种结构
很多场景要反复「取当前最小/最大值」，同时还在不断加入新元素：任务调度取优先级最高的、Dijkstra 取距离最近的点、合并 K 个有序链表取最小头节点。
如果用普通数组：每次取最小要扫全部 O(n)，或者维持全排序、插入要 O(n) 搬移。而二叉堆在「取极值 O(1) 观察、O(log n) 取出」和「插入 O(log n)」之间取得最佳平衡——它不追求全局有序（那太贵），只维护一个「堆顶必是极值」的弱有序，恰好够用。这就是 PriorityQueue 的价值：不是排序容器，是「极值维护器」。
二、用数组存树：下标寻址代替指针
二叉堆是一棵完全二叉树（除最后一层外全满，最后一层靠左排），这个特性让它能用数组紧凑存储、无需指针：
数组: [1, 3, 2, 7, 5, 4]
下标: 0 1 2 3 4 5
对应的树: 1(0)
/ \
3(1) 2(2)
/ \ /
7(3) 5(4) 4(5)
下标 i 的父 = (i-1)/2，左孩子 = 2i+1，右孩子 = 2i+2
如 i=4(值5): 父 = (4-1)/2 = 1(值3) ✓用数组的好处：内存连续、缓存友好、无指针开销，而且父子关系纯靠算术算出来。「完全二叉树」这个约束是关键——正因为它没有空洞，下标才能连续、公式才成立。
三、offer 上浮：新元素怎么找到位置
插入时先把元素放数组末尾（保持完全二叉树形态），再让它「上浮」到该待的地方。用数字走一遍，往小顶堆 [1,3,2,7,5,4] 插入 0：
① 放末尾 index=6: [1,3,2,7,5,4,0] 0 的父 = (6-1)/2 = 2(值2)
② 0 < 2，交换: [1,3,0,7,5,4,2] 0 到 index=2，父 = 0(值1)
③ 0 < 1，交换: [0,3,1,7,5,4,2] 0 到根，停止比较次数 = 树高 = log n。上浮只跟「一条从叶到根的路径」打交道，不碰其他分支，这是它 O(log n) 的原因。
四、poll 下沉：取走堆顶后如何修复
取最小值就是取走堆顶（index 0），但不能留个空洞。做法是把数组最后一个元素填到堆顶，再让它「下沉」：不断和两个孩子中较小的比，比孩子大就交换下去，直到不大于孩子或到叶子。
从 [0,3,1,7,5,4,2] poll:
① 取走堆顶 0，把末尾 2 填到顶: [2,3,1,7,5,4]
② 2 的孩子 3(左)、1(右)，较小是 1，2>1 交换: [1,3,2,7,5,4]
③ 2(现 index=2) 的孩子 4，2<4，停止
返回 0，堆恢复，新堆顶 1下沉每层选「较小的孩子」交换，保证换上来的仍是子树最小，维持堆性质。同样只走一条路径，O(log n)。
五、大顶堆、Top K 与经典应用
默认是小顶堆（自然序，最小先出）。要大顶堆，构造时传反向 Comparator：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());Top K 是最经典的考法，而且有个反直觉技巧——求「最大的 K 个」用小顶堆（不是大顶堆）：
求 100 万个数里最大的 10 个：
维护一个大小为 10 的小顶堆：
堆满后，每来一个数就和堆顶（当前 10 个里最小的）比：
比堆顶大 → poll 掉堆顶，offer 新数
比堆顶小 → 丢弃
最终堆里就是最大的 10 个。堆顶是这 10 个里最小的。
时间 O(n log K)，空间 O(K)——K 远小于 n 时，比全排序 O(n log n) 省得多其他应用：任务调度（优先级最高先执行）、Dijkstra/Prim（取最近节点）、合并 K 个有序链表、定时器（最近到期任务先触发）。
六、性能、陷阱与和其他结构对比
| 操作 | 复杂度 | 说明 |
|---|---|---|
| offer（入队） | O(log n) | 上浮 |
| poll（出队极值） | O(log n) | 下沉 |
| peek（看堆顶） | O(1) | 直接取 index 0 |
| 建堆（批量传入） | O(n) | 自底向上 heapify，比逐个 offer 的 O(n log n) 快 |
| contains / remove(任意值) | O(n) | 要线性扫描找元素 |
| 结构 | 出队顺序 | 取极值 |
|---|---|---|
| ArrayDeque（普通队列） | 先进先出 | 不支持直接取极值 |
| PriorityQueue | 按优先级（极值先出） | O(1) 看、O(log n) 取 |
| TreeSet/TreeMap | 完全有序遍历 | O(log n)，但增删也 O(log n) 且不能重复 |
两个关键陷阱：① PriorityQueue 允许重复元素但 TreeSet 不允许，需要「有重复 + 取极值」只能用堆；② 它线程不安全，多线程用 PriorityBlockingQueue。
记忆钩子：「数组存的完全二叉堆，offer 上浮、poll 下沉、堆顶恒极值」；求最大 K 个反而用小顶堆——记住这个「反着来」的技巧最能体现理解。
七、常见误区与追问
- 误区：PriorityQueue 是先进先出。 它按优先级出队（默认最小先出），完全不看进入顺序；FIFO 请用 ArrayDeque/LinkedList。
- 误区：遍历 PriorityQueue 能得到排序结果。 只有堆顶保证是极值，数组其余部分并非有序；要有序输出只能反复 poll。
- 误区：求最大 K 个用大顶堆。 求最大 K 个用大小为 K 的小顶堆（堆顶是这 K 个里最小的，便于淘汰）；求最小 K 个才用大顶堆。
- 误区：PriorityQueue 线程安全。 不安全，多线程场景用 PriorityBlockingQueue。
- 追问：建堆为什么是 O(n) 而不是 O(n log n)？ 用构造器批量传入时自底向上 heapify，底层节点多但下沉浅、顶层节点少但下沉深，加权求和收敛到 O(n)；逐个 offer 才是 O(n log n)。
- 追问：能存 null 吗？ 不能，null 无法参与优先级比较，offer(null) 抛 NPE。
- 追问：remove 一个中间元素多快？ O(n)，要先线性查找再下沉/上浮调整；堆擅长取极值，不擅长按值删除任意元素。
八、加强记忆
把 PriorityQueue 想成一个「永远把最小值托在顶上的沙漏」：底层是数组存储的完全二叉堆，靠 (i-1)/2、2i+1、2i+2 纯下标算父子，省掉指针还缓存友好。它不追求全局有序（太贵），只维护「堆顶恒是极值」的弱有序——offer 把新元素放末尾再沿一条路径上浮、poll 取走堆顶后拿末尾元素填顶再下沉，都是 O(log n)，看堆顶 O(1)。默认小顶堆，传反向 Comparator 变大顶堆。最爱考的是 Top K，且「求最大 K 个用大小 K 的小顶堆」这一反直觉技巧要记牢。它允许重复（TreeSet 不行）、但线程不安全（并发用 PriorityBlockingQueue）、也不能存 null。一句话收束：「堆顶恒极值，上浮下沉都 log n，取极值它最强、按值删它最弱」。