元数据卡

• 前置知识：堆（第7章前面部分）
• 核心难度：入门
• 完成标志：能用 PriorityQueue 解决 TopK 和合并有序流问题

---

上一节你手搓了一个堆——理解了上浮和下浮的每个细节。但实际工程中你很少从零实现堆。Java 标准库已经把它封装成 java.util.PriorityQueue。堆是剑的锻打过程，优先队列就是握在手里的剑柄。

---

破局：Java PriorityQueue

PriorityQueue 底层是一个最小堆。堆顶永远是优先级最高的元素（自然顺序下即最小值）。

// PriorityQueueDemo.java — 基本用法
// 编译：javac PriorityQueueDemo.java
// 运行：java PriorityQueueDemo

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5); pq.offer(3); pq.offer(8);
        pq.offer(1); pq.offer(7);

        System.out.println("堆顶: " + pq.peek());  // 1
        while (!pq.isEmpty())
            System.out.print(pq.poll() + " ");
        System.out.println();  // 1 3 5 7 8
    }
}

运行：javac PriorityQueueDemo.java && java PriorityQueueDemo。 预期输出：堆顶: 1，然后 1 3 5 7 8。

关键 API：

方法	行为	复杂度
offer(e)	插入（入队）	O(log n)
poll()	取出并删除堆顶（出队）	O(log n)
peek()	查看堆顶	O(1)

要做最大堆？传一个 Comparator.reverseOrder()：

// 最大堆
PriorityQueue<Integer> maxPq =
    new PriorityQueue<>(Comparator.reverseOrder());
maxPq.offer(5); maxPq.offer(3); maxPq.offer(8);
System.out.println(maxPq.poll()); // 8

运行：javac MaxHeapPriorityQueue.java && java MaxHeapPriorityQueue。 预期输出：8 5 3（倒序弹出的最小堆结果）。

reverseOrder() 反转了比较逻辑，让大的被认为"更优先"。

---

实战1：TopK——用最小堆求最大 K 个

兽道信使日处理 1 亿条消息，只关心最紧急的 100 条。全排序 O(n log n)？内存先撑不住。

这里用最小堆维护一个大小为 K 的窗口。堆顶是当前"第 K 大"的候选。新元素比堆顶大？加进来，踢走堆顶。最终堆里剩的就是前 K 大。

// TopK.java — 找前 K 大元素
// 编译：javac TopK.java
// 运行：java TopK

import java.util.PriorityQueue;
import java.util.Random;

public class TopK {
    public static int[] topK(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        for (int v : nums) {
            if (heap.size() < k) heap.offer(v);
            else if (v > heap.peek()) { heap.poll(); heap.offer(v); }
        }
        int[] res = new int[heap.size()];
        for (int i = 0; i < res.length; i++) res[i] = heap.poll();
        return res;
    }

    public static void main(String[] args) {
        Random rand = new Random(42);
        int[] logs = new int[1_000_000];
        for (int i = 0; i < logs.length; i++) logs[i] = rand.nextInt(100_000);
        int[] top = topK(logs, 100);
        System.out.print("前10: ");
        for (int i = top.length - 1; i >= top.length - 10; i--)
            System.out.print(top[i] + " ");
        System.out.println("\n大小: " + top.length);  // 100
    }
}

运行步骤：javac TopK.java && java TopK。时间复杂度 O(n log K)，空间 O(K)。为什么不用最大堆？最大堆堆顶是最大元素，你先 pop 就把最大的扔了——方向反了。

---

实战2：合并 K 个有序序列

几个侦察队各记录了一份有序敌情报告。你想合并成一份完整有序报告——每个列表已经排序，你只需要每次从所有列表头部选最小的那个。

// MergeKSorted.java — 合并 K 个有序数组
// 编译：javac MergeKSorted.java
// 运行：java MergeKSorted

import java.util.*;

public class MergeKSorted {
    static class Entry implements Comparable<Entry> {
        int val, listIdx, pos;
        Entry(int v, int li, int p) { val = v; listIdx = li; pos = p; }
        public int compareTo(Entry o) { return Integer.compare(val, o.val); }
    }

    public static List<Integer> merge(List<List<Integer>> lists) {
        PriorityQueue<Entry> heap = new PriorityQueue<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < lists.size(); i++)
            if (!lists.get(i).isEmpty())
                heap.offer(new Entry(lists.get(i).get(0), i, 0));
        while (!heap.isEmpty()) {
            Entry e = heap.poll();
            res.add(e.val);
            if (e.pos + 1 < lists.get(e.listIdx).size())
                heap.offer(new Entry(lists.get(e.listIdx).get(e.pos + 1),
                    e.listIdx, e.pos + 1));
        }
        return res;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = Arrays.asList(
            Arrays.asList(1, 4, 5),
            Arrays.asList(1, 3, 4),
            Arrays.asList(2, 6)
        );
        System.out.println(merge(lists));
        // [1, 1, 2, 3, 4, 4, 5, 6]
    }
}

运行：javac MergeKSorted.java && java MergeKSorted。时间 O(N log K)，空间 O(K)。

---

常见陷阱

PriorityQueue 不保证迭代顺序。 toString() 或 iterator() 的输出不是排序的。唯一正确的顺序读取方式是反复 poll()。

堆 vs 优先队列的关系。 面试可能会问。优先队列是抽象概念——一种出队时返回最高优先级元素的队列。堆是它的经典实现，但不是唯一实现（也可以用未排序链表：O(1) 入队、O(n) 出队）。

---

旅人笔记

PriorityQueue 的 API 只有 offer、poll、peek，却能解决 TopK、合并有序流、任务调度、Dijkstra 最短路径等一堆问题。记住那个反直觉的核心：用最小堆求最大 K 个。

下一步：图

堆帮你拿到了"最值"。但如果你想知道元素之间的全部关系——谁和谁相连、谁是通路、谁是孤岛——你需要图。

看第8章：图 →