堆与优先队列#
一句话答案#
堆是完全二叉树（大顶堆父≥子），插入/删除 O(logn)，建堆 O(n)；Java PriorityQueue 默认小顶堆。
核心要点
操作： 插入 O(logn) 上浮 / 删除堆顶 O(logn) 下沉 / 建堆 O(n)
Java： new PriorityQueue<>() 小顶堆，new PriorityQueue<>(Comparator.reverseOrder()) 大顶堆
应用： Top-K / 合并K个有序链表 / 中位数(大+小顶堆) / Dijkstra
建堆为什么是 O(n) 而非 O(nlogn)#
关键反差： 节点越多的层，下沉高度越小。自底向上建堆从最后一个非叶子节点开始，每个节点最多下沉到底，但「下沉代价」取决于该节点的高度 h（到叶子的层数），而不是整棵树的高度 logn。
按层分摊： 满二叉树共 n 个节点、高度 H≈logn。高度为 h 的节点数约为 n/2^(h+1)，每个这样的节点下沉代价 ≤ h。总代价：
关键级数收敛： 利用 $\sum_{h=0}^{\infty}\frac{h}{2^{h}}=2$（可由 $\sum x^h=\frac{1}{1-x}$ 求导后乘 x，代入 x=1/2 得到），故
直觉：占节点总数一半的叶子（最底层）下沉代价为 0，占 1/4 的次底层只下沉 1 层……代价大的节点极少，加权求和后被几何级数压成常数倍 n。
对比：逐个插入建堆才是 O(nlogn)
| 方式 | 每个元素代价 | 总复杂度 |
|---|---|---|
| 自底向上下沉（heapify） | 越底层越便宜，加权收敛 | O(n) |
| 逐个插入上浮 | 后插入的在底层、要上浮约 logn | O(nlogn) |
区别根源：下沉是「少数高节点贵、多数低节点便宜」，上浮是「多数后插入节点都在底层、都得爬 logn」，加权方向正好相反。建堆请用下沉法。
面试回答（2分钟版）
堆是一种完全二叉树，分大顶堆和小顶堆。大顶堆每个父节点都大于等于子节点，堆顶是最大值；小顶堆反过来。核心操作两个：插入时新元素放到末尾往上”上浮”，删除堆顶时把末尾元素放顶部往下”下沉”，都是O(logn)。建堆是从最后一个非叶子节点开始依次下沉，时间O(n)而不是O(nlogn)。Java中PriorityQueue默认是小顶堆，要大顶堆传Comparator.reverseOrder()。典型应用包括Top-K问题（求最大的K个用小顶堆，堆顶当门槛淘汰小的）、合并K个有序链表（堆维护K个链表头）、数据流求中位数（一个大顶堆一个小顶堆配合）、Dijkstra最短路。注意PriorityQueue不是线程安全的，并发场景要用PriorityBlockingQueue。
追问与易错
追问方向：
- “大顶堆和小顶堆怎么选？”→ 求 Top-K 最大用小顶堆（堆顶是最小值，不够大的被淘汰），求 Top-K 最小用大顶堆；求中位数同时维护一个大顶堆和一个小顶堆
- “堆排序为什么不如快排常用？”→ 堆排序缓存不友好（数组跳跃访问局部性差）导致实际运行慢于快排；且堆排序不稳定，常数因子大，虽然最坏 O(nlogn) 但实测通常比快排慢 2-3 倍
- “Java PriorityQueue 是线程安全的吗？”→ 不是，PriorityQueue 非线程安全；并发场景用 PriorityBlockingQueue（阻塞队列，基于锁）或手动加锁
- “建堆为什么是 O(n) 不是 O(nlogn)？”→ 自底向上下沉，高度为 h 的节点有 n/2^(h+1) 个、下沉代价 ≤h，总代价 = (n/2)·Σh/2^h；级数 Σh/2^h 收敛到 2，故总代价 ≤ n，即 O(n)。而逐个插入上浮是 O(nlogn)，因为大多数节点在底层、上浮要爬 logn
易错点：
- ❌ 堆就是完全排序的——堆只保证堆顶最大/最小
- ❌ PriorityQueue 是线程安全的——不是需要 PriorityBlockingQueue