PriorityQueue 底层与二叉堆：五个递进问题，从队列差异问到十亿级 Top100
单元 1-3 的集合选型里，PriorityQueue 只讲了一句话的结论：底层是二叉堆，只维护「堆顶最小」这一条弱序，offer 上浮、poll 下沉都是 O(log n)。但它凭什么做到每次 poll 都吐出当前最小，堆在数组里到底怎么站队，面试官不会让你背结论，他会顺着一条线往下问：先问它和 LinkedList 同为 Queue 为何行为相反，再问内部怎么保证有序，然后甩一句别用 PriorityQueue 手写 add 和 poll，接着考你把「取最小」改成「取最大的 Top K」，最后用十亿条数据找最大一百个收尾。这篇就把这五个递进问题一次讲透：每题先给可复现代码、再贴本机 JDK 26.0.1 的真实输出，代码放在它被讲到的位置，可以边读边跑。手写堆的对拍、Top K 的门槛推演、以及十亿数据的单遍扫描，全部有真实运行结果垫底，不是默写。
第一问（基础）：PriorityQueue 和 LinkedList 都实现了 Queue，为什么出队顺序不一样
面试的第一个问题常常轻飘飘的，但它不是考 API，是考你有没有意识到一件事：Queue 接口不承诺任何顺序，FIFO 只是 LinkedList 的顺带结果，不是队列的定义。两个类都 offer、poll、peek，签名一模一样，可一旦底层存储形态不同，这三个操作的行为就分道扬镳。
LinkedList 底层是双向链表，元素一个接一个用 first/last 指针串起来，offer 往尾巴挂、poll 从头摘，所以它天然是先进先出；它同时还实现了 List 和 Deque，按下标访问、在任意位置插入删除都行，允许 null。PriorityQueue 底层不是链表也不是有序数组，而是一棵二叉堆，offer 之后元素按「谁小谁靠前」的优先级排，poll 每次摘走当前最小的那个；它不保证先进先出、不支持按下标访问、不允许 null。同样是 offer(5)、offer(3)、offer(8)、offer(1) 这四个数，两边的出队序列完全相反：
import java.util.*;
/** 同一个入队序列, LinkedList 与 PriorityQueue 的出队差异 */
public class Q1_QueueDiff {
public static void main(String[] args) {
int[] data = { 5, 3, 8, 1 }; // 就按 5->3->8->1 的顺序进
LinkedList<Integer> ll = new LinkedList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : data) { ll.offer(x); pq.offer(x); }
System.out.println("入队顺序 : 5 -> 3 -> 8 -> 1");
System.out.println("LinkedList.poll : " + pollAll(ll));
System.out.println("PriorityQueue.poll: " + pollAll(pq));
// 只看不出队时, 队首是谁
LinkedList<Integer> ll2 = new LinkedList<>();
PriorityQueue<Integer> pq2 = new PriorityQueue<>();
for (int x : new int[] { 3, 1, 2 }) { ll2.offer(x); pq2.offer(x); }
System.out.println("LinkedList.peek : " + ll2.peek() + " (FIFO, 先进队的 3 在队首)");
System.out.println("PriorityQueue.peek: " + pq2.peek() + " (最小堆, 1 在堆顶)");
}
static String pollAll(Queue<Integer> q) {
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) sb.append(q.poll()).append(" ");
return sb.toString();
}
}入队顺序 : 5 -> 3 -> 8 -> 1
LinkedList.poll : 5 3 8 1
PriorityQueue.poll: 1 3 5 8
LinkedList.peek : 3 (FIFO, 先进队的 3 在队首)
PriorityQueue.peek: 1 (最小堆, 1 在堆顶)两个容器都叫队列，但它们回答的是两种不同的需求：LinkedList 是「谁先来谁先走」的时间队列，PriorityQueue 是「谁更紧急谁先走」的优先级队列。peek 是只看不出，最能暴露差异——LinkedList 的队首永远是最早进来的那个（这里的 3，因为 3 先进），PriorityQueue 的堆顶永远是当前最小的那个（这里的 1，虽然它最后才进）。面试答到这里，点出「Queue 接口不承诺 FIFO，顺序由底层结构决定」，第一问就过关了。
第二问（原理）：它是怎么保证每次 poll 出来的都是最小值 —— 二叉堆的数组形态
第一问的代码里藏着一个反直觉的现象：PQ 一共 poll 出 1 3 5 8，看着像排好序了，但你要是以为它内部维护了一个随时排好序的数组，那就掉坑了——排序数组的插入是 O(n) 的搬移，十个元素感觉不到，十万个就露馅。PriorityQueue 的 O(log n) 靠的是另一套存储：二叉堆。
二叉堆是「一棵完全二叉树平铺进数组」：除了最后一层，每层都填满，最后一层从左往右填。把它按层序遍历放进数组后，就得到一套不用存指针的下标寻亲公式（JDK 的堆数组从下标 0 开始）：
- 下标
i的父节点 =(i - 1) / 2 - 下标
i的左孩子 =2i + 1，右孩子 =2i + 2
堆只维护一条不变量：父节点不大于子节点（最小堆）。这是一条很弱的序——它只约束父子，不约束兄弟，所以数组里 a[0]（树根）必须是全局最小，但数组整体并不是有序的。offer 和 poll 就围绕这条不变量做修复：
- offer（入队）：新元素先塞到数组末尾（对应完全二叉树的最后一个空位），然后一路上浮（sift-up）——只要它比父节点小，就往上换，直到站到父不大于它的位置。
- poll（出队）：堆顶
a[0]就是要出的最小值，直接拿走；但树不能空出个根，于是把数组末尾的元素挪到根部，再让它一路下沉（sift-down）——跟两个儿子里较小的比，比儿子大就往下换，直到它不大于两个儿子。 - peek（只看不出）：返回
a[0]，O(1)。
上浮和下沉每次最多走树高那么远，而完全二叉树的高度是 log₂n，所以 offer/poll 都是 O(log n)。堆顶永远是最小值这一点，就保证每次 poll 吐出的都是当前最小。
只看文字还是抽象。PriorityQueue 的内部数组是私有的，但它的 toArray() 返回的正是这个堆序数组的副本——所以不用反射，直接观察它就能看到堆的真实形态。把 5、3、8、1、4、9、2、7、6、0 依次 offer，每步打印内部数组：
import java.util.*;
/**
* 用 toArray()(返回内部堆数组副本)观察 PriorityQueue:
* 数组并不是"排好序"的, 但父节点永远 <= 子节点, 根 a[0] 恒为最小。
*/
public class Q2_HeapState {
public static void main(String[] args) {
int[] in = { 5, 3, 8, 1, 4, 9, 2, 7, 6, 0 };
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : in) {
pq.offer(x);
System.out.println("offer " + x + " -> " + Arrays.toString(pq.toArray()));
}
System.out.println("size=" + pq.size() + ", peek 最小=" + pq.peek());
while (!pq.isEmpty()) {
int m = pq.poll();
System.out.println("poll " + m + " -> " + Arrays.toString(pq.toArray()));
}
}
}offer 5 -> [5]
offer 3 -> [3, 5]
offer 8 -> [3, 5, 8]
offer 1 -> [1, 3, 8, 5]
offer 4 -> [1, 3, 8, 5, 4]
offer 9 -> [1, 3, 8, 5, 4, 9]
offer 2 -> [1, 3, 2, 5, 4, 9, 8]
offer 7 -> [1, 3, 2, 5, 4, 9, 8, 7]
offer 6 -> [1, 3, 2, 5, 4, 9, 8, 7, 6]
offer 0 -> [0, 1, 2, 5, 3, 9, 8, 7, 6, 4]
size=10, peek 最小=0
poll 0 -> [1, 3, 2, 5, 4, 9, 8, 7, 6]
poll 1 -> [2, 3, 6, 5, 4, 9, 8, 7]
poll 2 -> [3, 4, 6, 5, 7, 9, 8]
poll 3 -> [4, 5, 6, 8, 7, 9]
poll 4 -> [5, 7, 6, 8, 9]
poll 5 -> [6, 7, 9, 8]
poll 6 -> [7, 8, 9]
poll 7 -> [8, 9]
poll 8 -> [9]
poll 9 -> []这串输出信息量很大，挑两个时刻细看。offer 全部结束后数组是 [0, 1, 2, 5, 3, 9, 8, 7, 6, 4]——它不是排序数组（看 9, 8, 7 就不是升序），但它是合法的堆。套下标公式验证：根 0 的两个孩子是下标 1 的 1 和下标 2 的 2，满足 0 ≤ 1, 0 ≤ 2；下标 1 的 1，两个孩子是下标 3 的 5 和下标 4 的 3，满足 1 ≤ 5, 1 ≤ 3；下标 4 的 3，孩子是下标 9 的 4，满足 3 ≤ 4。画成树就是：
0
/ \
1 2
/ \ / \
5 3 9 8
/ \ /
7 6 4每个父节点都不大于它的子节点，所以根 0 一定全局最小，peek 直接返回它。注意 offer 2 那一步：2 塞到末尾（下标 6）时它左边是 9，树上是 2 的孩子；2 比父 8 小，往上换到下标 2 的位置——数组从 [1,3,8,5,4,9,2] 变成 [1,3,2,5,4,9,8]，这就是一次上浮。
poll 阶段每次拿走堆顶后，看剩余数组的第一位是不是逐步增大：0 出完后堆顶变 1，1 出完变 2……每次拿走的都是当时的最小值，所以 poll 序列严格升序 0 1 2 ... 9，这就是第二问的完整答案。堆不是把数据排好序等你来取，它只承诺一件事：根是极值。取一个、修一次，每次修复代价 O(log n)。
第三问（手撕）：不让你用 PriorityQueue，手写一个堆实现 add 和 poll
面试到这里会突然没收你的轮子：既然你背得出上浮下沉，那请你不用 PriorityQueue，白板写一个最小堆，实现 add（等价 offer）和 poll。这题没有技巧，就是考第二问那两条修复路径的代码能不能落地。核心只有三块：数组加元素个数、add 里一趟上浮、poll 里一趟下沉。我自己写了一份（JDK 26.0.1 环境下跑通），全文如下：
import java.util.*;
/**
* 手写最小堆（小顶堆）。
* 二叉堆的数组布局：根在下标 0。
* 下标 i 的左右孩子 = 2i+1, 2i+2；父 = (i-1)/2。
* 不变量：父 <= 子（最小堆），所以 a[0] 永远是当前最小。
*/
public class Q3_MyHeap {
private int[] a = new int[16];
private int n = 0; // 当前元素个数
private void ensure() {
if (n == a.length) a = Arrays.copyOf(a, a.length * 2);
}
/** add = 放到数组末尾，然后一路"上浮"：比自己父小就和父换，直到站对位置。 */
public void add(int x) {
ensure();
a[n] = x;
int i = n;
n++;
// sift-up 上浮
while (i > 0) {
int p = (i - 1) / 2;
if (a[p] <= a[i]) break; // 父已 <= 子，堆序满足，停
swap(p, i);
i = p;
}
}
/** poll = 把堆顶拿走，把末尾元素搬到根，然后一路"下沉"。 */
public int poll() {
if (n == 0) throw new NoSuchElementException();
int top = a[0];
n--;
a[0] = a[n]; // 末位元素顶替根
// sift-down 下沉
int i = 0;
while (true) {
int l = 2 * i + 1, r = 2 * i + 2;
int smallest = i;
if (l < n && a[l] < a[smallest]) smallest = l;
if (r < n && a[r] < a[smallest]) smallest = r;
if (smallest == i) break; // 已比两个儿子都小，站对位置
swap(i, smallest);
i = smallest;
}
return top;
}
public int peek() { return a[0]; }
public boolean isEmpty() { return n == 0; }
public int size() { return n; }
private void swap(int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
// ===== 对拍：和 JDK 的 PriorityQueue 喂同样的数据，看输出是否一致 =====
public static void main(String[] args) {
int[] in = { 5, 3, 8, 1, 4, 9, 2, 7, 6, 0 };
Q3_MyHeap mine = new Q3_MyHeap();
PriorityQueue<Integer> jdk = new PriorityQueue<>();
for (int x : in) {
mine.add(x);
jdk.offer(x);
}
System.out.println("我的堆 peek = " + mine.peek() + " | JDK peek = " + jdk.peek());
StringBuilder s1 = new StringBuilder();
while (!mine.isEmpty()) s1.append(mine.poll()).append(" ");
StringBuilder s2 = new StringBuilder();
while (!jdk.isEmpty()) s2.append(jdk.poll()).append(" ");
System.out.println("我的堆出队: " + s1);
System.out.println("JDK 出队: " + s2);
System.out.println("两者一致: " + s1.toString().equals(s2.toString()));
// 用单调性自查: 出队必须非降序 (最小堆的承诺)
Q3_MyHeap h3 = new Q3_MyHeap();
Random rnd = new Random(42);
for (int i = 0; i < 100000; i++) h3.add(rnd.nextInt(1000000));
int prev = Integer.MIN_VALUE;
boolean asc = true;
while (!h3.isEmpty()) {
int v = h3.poll();
if (v < prev) { asc = false; break; }
prev = v;
}
System.out.println("100000 个随机数出队全程非降序: " + asc);
}
}我的堆 peek = 0 | JDK peek = 0
我的堆出队: 0 1 2 3 4 5 6 7 8 9
JDK 出队: 0 1 2 3 4 5 6 7 8 9
两者一致: true
100000 个随机数出队全程非降序: true对着代码抠两个最容易写错的点。第一处是 add 的上浮循环，终止条件必须是 a[p] <= a[i] 就 break——意思是「我已经不比父大（或相等），堆序满足了」，等价写法是只在 a[i] < a[p] 时才交换，两者别混；有人手滑写成 < 判断、漏了相等情况，相等的兄弟会反复上浮甚至死循环。第二处是 poll 的下沉要先找两个儿子里较小的那个再比。最小堆里父要跟「更小的儿子」换，才能保证换完父依然不大于另一个儿子。判断时先用 l < n 保证左儿子存在（n 是当前元素个数，数组 [0, n) 有效），再比较左、右哪个更小，如果最小的还是自己就 break。整段代码没有递归，纯两个 while 循环——这是白板手写最稳妥的形态，不容易爆栈也不容易写乱。
对拍结果说明这个手写堆和 JDK 的 PriorityQueue 行为完全一致，100000 个随机数出队全程非降序，也反向验证了第二问的承诺。手写这题，白板前讲清三句话就能收：数组存完全二叉树、add 末尾上浮、poll 根下沉，每次修复沿树高走，O(log n)。
第四问（扩展）：如果我要取的是最大的 Top K，怎么改
前三问都在「取最小」上打转，第四问突然翻面：现在要最大的 Top K。很多人第一反应是「把比较器反过来不就行了」，这只对了一半。翻面有两种改法，适用场景完全不同，面试官要听你把它们分开。
改法一：数据量不大、已经全部在内存里，反转比较器让堆顶变成最大，再连 poll K 次。 PriorityQueue 默认是最小堆，传 Comparator.reverseOrder() 比较器就把大小关系整个倒过来，堆变成大顶堆，堆顶是当前最大，poll 一次拿一个最大，连 poll K 次就得到降序的前 K 大：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (int x : data) maxHeap.offer(x); // data = {5,3,8,1,4,9,2,7,6,0}
StringBuilder a = new StringBuilder();
for (int i = 0; i < K; i++) a.append(maxHeap.poll()).append(" "); // K = 3
System.out.println("反转比较器装全部, 连 poll 3 次 -> " + a);反转比较器装全部, 连 poll 3 次 -> 9 8 7 这套代码直白好懂，但注意它把全部数据都装进了堆：内存是 O(n)，offer 是 O(n log n)。要是数据本身是个读不完的流，或者有十亿条（下一问），这套就炸了。
改法二：真正的 Top K 解法——只留容量为 K 的小顶堆当门槛。 这是最反直觉也最关键的一步：要取「最大的 K 个」，我偏偏不用大顶堆，而是用一个容量只有 K 的小顶堆。堆顶是这个堆里最小的那个，正好充当「当前第 K 大的门槛」：新元素要是比堆顶还小，说明它连前 K 都进不了，直接丢；要是比堆顶大，就把堆顶挤出去、自己进来，再上浮回正。这样从头到尾堆里只养 K 个元素，内存 O(K)，扫描一遍数据 O(n log K)。跑一遍看门槛怎么一步步抬上去的：
import java.util.*;
/** Top-K 两套改法: A 反转比较器取最大; B 容量=K 的小顶堆当"门槛" */
public class Q4_TopK {
public static void main(String[] args) {
int[] data = { 5, 3, 8, 1, 4, 9, 2, 7, 6, 0 };
int K = 3;
// 改法 A: 反转比较器 -> 大顶堆, 堆顶是最大。装全部再连 poll K 次
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (int x : data) maxHeap.offer(x);
StringBuilder a = new StringBuilder();
for (int i = 0; i < K; i++) a.append(maxHeap.poll()).append(" ");
System.out.println("改法A 反转比较器(装全部, 再poll " + K + " 次): " + a);
// 改法 B: 容量 K 的小顶堆当门槛。堆顶 = 当前第 K 大
PriorityQueue<Integer> top = new PriorityQueue<>(); // 注意仍是"小顶堆"
for (int x : data) {
if (top.size() < K) {
top.offer(x);
System.out.println(" " + x + " 直接进堆(还没满 " + K + ") -> 堆顶=门槛" + top.peek() + " " + top);
} else if (x > top.peek()) { // 比门槛大才替换
top.poll();
top.offer(x);
System.out.println(" " + x + " > 门槛, 挤掉堆顶后进堆 -> 堆顶=门槛" + top.peek() + " " + top);
} else {
System.out.println(" " + x + " <= 门槛" + top.peek() + ", 直接丢弃 -> " + top);
}
}
List<Integer> sorted = new ArrayList<>(top);
Collections.sort(sorted);
System.out.println("改法B 收尾: 堆内=" + top + " (堆顶=" + top.peek() + " = 第" + K + "大/门槛), 排好序=最大的 " + K + " 个 -> " + sorted);
}
}改法A 反转比较器(装全部, 再poll 3 次): 9 8 7
5 直接进堆(还没满 3) -> 堆顶=门槛5 [5]
3 直接进堆(还没满 3) -> 堆顶=门槛3 [3, 5]
8 直接进堆(还没满 3) -> 堆顶=门槛3 [3, 5, 8]
1 <= 门槛3, 直接丢弃 -> [3, 5, 8]
4 > 门槛, 挤掉堆顶后进堆 -> 堆顶=门槛4 [4, 8, 5]
9 > 门槛, 挤掉堆顶后进堆 -> 堆顶=门槛5 [5, 8, 9]
2 <= 门槛5, 直接丢弃 -> [5, 8, 9]
7 > 门槛, 挤掉堆顶后进堆 -> 堆顶=门槛7 [7, 9, 8]
6 <= 门槛7, 直接丢弃 -> [7, 9, 8]
0 <= 门槛7, 直接丢弃 -> [7, 9, 8]
改法B 收尾: 堆内=[7, 9, 8] (堆顶=7 = 第3大/门槛), 排好序=最大的 3 个 -> [7, 8, 9]看门槛那列：3 → 4 → 5 → 7，一路往上抬，因为能挤进前 3 的门槛只会越来越高。前 3 个直接进堆、门槛是堆里最小的 3；到 1 时它比门槛 3 小，说明数据里已经有 3 个比 1 大了，1 进不了前三，丢；4 比门槛 3 大，挤掉 3 进来，门槛抬到 4；9 比门槛 4 大，挤掉 4，门槛抬到 5。最后堆里 [7, 9, 8] 就是最大的三个，堆顶 7 恰好是第 3 大。整段代码里唯一的堆就是默认的小顶堆，new PriorityQueue<>(K) 只是预分配容量，没有反转任何比较器——这就是 Top K 的反直觉点：大顶堆是「装全部再吐最大」，小顶堆门槛是「只留 Top K」，数据量大时后者才是答案。
所以第四问的标准回答是分两句：数据已全量在内存、要降序结果，反转比较器加大顶堆连 poll K 次，O(n log n)；数据是流或规模大，用容量 K 的小顶堆做门槛单遍扫描，O(n log K) 时间 O(K) 内存。要取「最小的 Top K」时对称地换成大顶堆门槛即可。面试里能主动补出第二句的人，基本就锁定这道题了。
第五问（终极）：十亿条数据找最大的 100 个，内存放不下怎么办
最后一问把规模拉到十亿。先戳破一个表述陷阱：「内存放不下」指的是装不下十亿条原始数据，不是装不下答案——答案只要 100 个。第四问的改法二已经是正确骨架：用一个容量只有 100 的小顶堆，从头到尾扫一遍，内存恒为 O(100)，跟数据总量 N 一点关系都没有。十亿条听起来吓人，其实只需要能放 100 个数的堆加一个顺序读的源。为了在本地复现「读不完的流」，我用线性同余伪随机生成器 LCG 现场产数、不落数组，喂给容量 100 的小顶堆：
import java.util.*;
/**
* 海量数据 Top100: 单机一条流 + 容量为 100 的小顶堆, 内存 O(100)。
* 数据源用 LCG(线性同余)伪随机生成器模拟"读不完的流", 不落数组。
* 演示三件事:
* (1) 小样本用全排序对拍, 证明"容量100的小顶堆"结果正确;
* (2) 把 N 拉到 10 亿, 内存占用仍是 O(100), 时间线性;
* (3) 数据被切成 P 片(如分布多台机器/多个文件)时: 每片先算各自 Top100,
* 再在候选集(<= P*100 个)上归并, 与整流单遍结果一致。
*/
public class Q5_MassiveTop100 {
// ---- LCG: x_{n+1} = a*x_n + c (mod 2^31), 足够快且可复现 ----
static final long A = 1664525L, C = 1013904223L;
/** 消费 [seed 起连续 n 个] 的流, 喂给容量 k 的小顶堆, 返回堆 */
static PriorityQueue<Integer> streamTopK(long n, int k, long seed) {
PriorityQueue<Integer> heap = new PriorityQueue<>(k);
long s = seed;
for (long i = 0; i < n; i++) {
s = (A * s + C) & 0x7fffffffL;
int x = (int) s;
if (heap.size() < k) heap.offer(x);
else if (x > heap.peek()) { heap.poll(); heap.offer(x); }
}
return heap;
}
static Integer[] sorted(PriorityQueue<Integer> h) {
Integer[] a = h.toArray(new Integer[0]);
Arrays.sort(a);
return a;
}
public static void main(String[] args) {
int K = 100;
long seed = 20260904L;
// ---------- (1) 小样本对拍: 单遍小顶堆 vs 全排序 ----------
long n1 = 2_000_000L;
Integer[] got = sorted(streamTopK(n1, K, seed));
int[] all = new int[(int) n1];
long s = seed;
for (int i = 0; i < n1; i++) { s = (A * s + C) & 0x7fffffffL; all[i] = (int) s; }
Arrays.sort(all);
int[] ref = Arrays.copyOfRange(all, all.length - K, all.length);
Integer[] refW = new Integer[K];
for (int i = 0; i < K; i++) refW[i] = ref[i];
System.out.println("(1) 小样本 N=" + n1 + " 对拍:");
System.out.println(" sort 前100大 = [" + refW[0] + " ... " + refW[K - 1] + "] (第100大=" + refW[0] + ", 最大=" + refW[K - 1] + ")");
System.out.println(" 小顶堆 Top100 = [" + got[0] + " ... " + got[K - 1] + "]");
System.out.println(" 结果一致: " + Arrays.equals(refW, got));
// ---------- (2) N = 10 亿, 单条流 ----------
long n2 = 1_000_000_000L;
long t0 = System.currentTimeMillis();
Integer[] big = sorted(streamTopK(n2, K, seed));
long ms = System.currentTimeMillis() - t0;
System.out.println("\n(2) N=10亿 单条流扫描: 耗时 " + ms + " ms");
System.out.println(" 堆内元素数=" + big.length + " (恒 ≤ " + K + ", 与 N 无关)");
System.out.println(" 第100大(门槛)=" + big[0] + " 最大=" + big[K - 1]);
System.out.println(" 最大前5个 = " + Arrays.toString(Arrays.copyOfRange(big, big.length - 5, big.length)));
Runtime rt = Runtime.getRuntime();
System.out.println(" 全程 JVM 堆占用约 "
+ ((rt.totalMemory() - rt.freeMemory()) / 1024 / 1024) + " MB (含 JVM 自身)");
// ---------- (3) 把同一条流切 P 片, 各算 Top100, 再归并 ----------
int P = 16;
long n3 = 2_000_000L;
long chunk = n3 / P;
List<Integer> cand = new ArrayList<>(); // <= P*K 个候选
long state = seed;
for (int p = 0; p < P; p++) {
PriorityQueue<Integer> part = new PriorityQueue<>(K);
for (long i = 0; i < chunk; i++) {
state = (A * state + C) & 0x7fffffffL;
int x = (int) state;
if (part.size() < K) part.offer(x);
else if (x > part.peek()) { part.poll(); part.offer(x); }
}
cand.addAll(part); // 每片留下自己的 Top100
}
PriorityQueue<Integer> mergeHeap = new PriorityQueue<>(K);
for (int x : cand) {
if (mergeHeap.size() < K) mergeHeap.offer(x);
else if (x > mergeHeap.peek()) { mergeHeap.poll(); mergeHeap.offer(x); }
}
Integer[] merged = sorted(mergeHeap);
System.out.println("\n(3) 同一条流切 " + P + " 片, 每片本地 Top100 再归并:");
System.out.println(" 候选集大小=" + cand.size() + " (≤ P*K=" + (P * K) + ")");
System.out.println(" 归并 Top100 = [" + merged[0] + " ... " + merged[K - 1] + "] (第100大=" + merged[0] + ")");
System.out.println(" 与整流单遍一致: " + Arrays.equals(merged, refW));
}
}(1) 小样本 N=2000000 对拍:
sort 前100大 = [2147363596 ... 2147483079] (第100大=2147363596, 最大=2147483079)
小顶堆 Top100 = [2147363596 ... 2147483079]
结果一致: true
(2) N=10亿 单条流扫描: 耗时 2256 ms
堆内元素数=100 (恒 ≤ 100, 与 N 无关)
第100大(门槛)=2147483428 最大=2147483645
最大前5个 = [2147483634, 2147483636, 2147483637, 2147483642, 2147483645]
全程 JVM 堆占用约 10 MB (含 JVM 自身)
(3) 同一条流切 16 片, 每片本地 Top100 再归并:
候选集大小=1600 (≤ P*K=1600)
归并 Top100 = [2147363596 ... 2147483079] (第100大=2147363596)
与整流单遍一致: true三个结果各有各的用处。第 (1) 段用 200 万条做全排序对拍，证明「容量 100 的小顶堆」抓出来的确实是前 100 大，方法本身没错；第 (2) 段把 N 顶到 10 亿，单遍扫描本机实测 2 秒出头（同一程序多跑几次在 2 到 4 秒浮动，是 JIT 和 GC 的正常抖动），全程堆里就 100 个元素、JVM 总占用约 10 MB——内存和 N 无关，这是 Top K 比全排序强的本质。注意这 10 MB 是纯计算，真实场景的瓶颈通常在读盘或拉数据的 IO，不在这 100 个数的堆上。
第 (3) 段回答「万一单机也扛不住、数据本来就在多台机器/多个文件上」怎么办——这就是面试里那层「外部」的含义。做法是分而治之的归并：把整条流切成 P 片，每片各自用容量 100 的小顶堆算出本片的 Top100（map），于是得到至多 P×100 个候选，再在这批候选上用同一个容量 100 的小顶堆归并一次（reduce），就是全局 Top100。它为什么是对的，可以用反证法一句话讲清：假设全局前 100 里有个元素 x，却没进它所在分区的本片 Top100——那说明它那片里至少有 100 个比 x 大的元素，这 100 个加 x 本身就已经超过 100 个比 x 大的了，x 不可能在全局前 100，矛盾。所以每片只留 Top100、丢其余，绝不会误伤全局 Top100，候选集被压到 P×100 个以内，第 (3) 段实测 16 片归并与整流单遍结果逐位一致。
把这个归并思路落到真正的「外部排序」术语上：当数据因为太大只能放磁盘、或天然分散在多台机器时，你说的两种招法其实是一件事的两层——小顶堆门槛是单点扫描的引擎，分片归并是把引擎并行化/外置化。如果需求只是 Top 100，从不需要把十亿条完整排好序，分片各自算 Top100 再归并就够，复杂度 O(N/P × log100) 每片、归并 O(P×100×log100)，规模上不封顶。只有当需求退化成「要把全部数据排好序输出」（比如全量报表、分页必须全局有序）时，才需要真正的外部归并排序：把磁盘数据切成能装进内存的块，每块内部快排写出，再对多个有序块做 K 路归并（K 路归并的挑最小，正是套一个容量 K 的小顶堆）——外部排序的归并段天生就是一堆有序文件在喂堆。所以终极答案是一条递进链：
- 内存装得下但很多：容量 K 小顶堆单遍扫，O(N log K) 时间、O(K) 内存；
- 内存装不下/多机：分片每片本地 Top100，候选集归并取全局 Top100；
- 必须全量有序：才上外部归并排序，归并段挑最小就是小顶堆的活。
从第一问的 FIFO 差异到这层外部归并，整条线其实只在一件事上打转：PriorityQueue 不是帮你排序的容器，它只维护一个可以 O(log n) 更新、O(1) 读取的极值口子。围绕这个口子，你能手写出它的骨架，能用它做流式 Top K，也能用它解释分布式归并——四个姿势就是五连问的全部。
面试速答：五连问压缩版
Q：PriorityQueue 和 LinkedList 作为队列有什么区别？
A：Queue 接口不承诺 FIFO，顺序由底层决定。LinkedList 底层双向链表，offer 挂尾、poll 摘头，先进先出，还实现了 List/Deque，支持下标访问和 null；PriorityQueue 底层二叉堆，谁小谁先出，不支持下标访问、不允许 null。同是 offer 5,3,8,1，LinkedList poll 出 5 3 8 1，PriorityQueue 出 1 3 5 8。
Q：它怎么保证每次 poll 都是最小值？
A：二叉堆，完全二叉树平铺进数组，父下标 (i-1)/2、孩子 2i+1/2i+2，只维护一条弱序「父≤子」，所以根 a[0] 恒为最小。offer 塞末尾后上浮修复，poll 拿根后用末位元素顶替再下沉修复，都沿树高走 O(log n)，peek O(1)。数组本身不是有序的，只保证堆顶是极值。
Q：手写 add 和 poll？
A：add 放数组末尾，while 里和父 (i-1)/2 比，父大就换、否则 break；poll 先判空，取 a[0]，把 a[n-1] 挪到根部，while 里跟两个儿子（2i+1、2i+2）中较小的比，儿子小就换、否则 break。两份代码都没递归，纯循环。用数组加 n 记长度，满了翻倍。
Q：要取最大的 Top K 怎么改？
A：看数据规模分两种。数据已全量在内存要降序结果：反转比较器成大顶堆，连 poll K 次，O(n log n)；数据是流或规模大：保持容量 K 的小顶堆当门槛，新元素比堆顶大才挤掉堆顶，单遍扫描 O(n log K) 时间、O(K) 内存。要最小的 Top K 就对称换成大顶堆门槛。
Q：十亿条找最大 100，内存放不下怎么办？
A：放不下的是原始数据，答案只要 100 个。单机单遍：容量 100 的小顶堆扫全量，内存 O(100)，本机实测十亿条纯计算 2 到 4 秒、JVM 约 10 MB。多机/多文件：切成 P 片，每片本地 Top100（map），候选集至多 P×100，再归并一次（reduce）得全局 Top100，正确性用反证法保证。只有必须把全部数据排好序输出时才上外部归并排序，归并段挑最小正是小顶堆的活。