专题 17堆（优先队列）：永远快速拿到最值

17.1堆是什么，Java 里怎么用

堆（Heap）本质是一棵完全二叉树，并且满足一个关键性质：父节点的值 ≤ 子节点的值（小顶堆）；反过来如果父 ≥ 子，就叫大顶堆。 「完全二叉树」的意思是：除了最后一层，上面各层都填满，最后一层从左往右排，中间不空。这个形状保证它可以用数组紧凑存储，不需要真的去建一棵链式树。

为什么这个性质有用？因为「父 ≤ 子」意味着整棵树最小的那个元素一定在根。所以无论是插一个元素还是删一个元素，只要维护好「堆性质」，我们就能在 O(log n) 时间拿到最值，而不用像数组那样扫一遍 O(n)。

小顶堆（父 ≤ 子）的样子：
        1
      /   \
     3     2
    / \   / \
   5   4 6   7
堆顶（根）= 1，永远是整棵树最小。

用数组存（下标从 0 开始，左孩子 2i+1，右孩子 2i+2，父亲 (i-1)/2）：
  [1, 3, 2, 5, 4, 6, 7]
   i=0  1  2  3  4  5  6

关键点：堆只保证「根是最值」，不保证整体有序！
        比如 3 和 2 谁大堆不管，只管 1 比它们都小。

Java 里怎么用：PriorityQueue

Java 标准库没有叫「Heap」的类，但 PriorityQueue 就是堆（优先队列）的实现。它默认是小顶堆（队头是最小元素）。常用三个操作：

• add(x) / offer(x)：插入元素，内部自动上浮维持堆性质，O(log n)；
• poll()：弹出堆顶（最值），内部自动把最后一个元素移到根再下沉，O(log n)；
• peek()：只看堆顶不删除，O(1)。

// 默认小顶堆：peek() 永远是最小元素
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5); minHeap.add(1); minHeap.add(3);
System.out.println(minHeap.peek()); // 输出 1

// 想要大顶堆：传入比较器，让「大的」排到前面
// 写法一：lambda (a,b)->b-a（注意整数溢出风险，见 17.7）
PriorityQueue<Integer> maxHeap1 = new PriorityQueue<>((a, b) -> b - a);
// 写法二：更安全的 Comparator.reverseOrder()
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap2.add(5); maxHeap2.add(1); maxHeap2.add(3);
System.out.println(maxHeap2.peek()); // 输出 5

17.2堆的三种典型用法

刷题时堆几乎只干三件事，认准这三类你就知道该不该用堆：

① Top K 问题：维护一个固定大小为 K 的堆

比如「前 K 个最大的数」。思路是：建一个大小为 K 的堆，扫一遍数组，把元素往里塞；堆满了就弹出最值，最后堆里剩下的就是 Top K。 具体用大顶还是小顶，取决于你要「最大」还是「第 K 大」——这个最容易想反，17.3 会专门讲。

② 多路归并：K 个有序序列合并

比如 K 个已经排好序的链表/数组，要把它们合成一个有序序列。每次只需要从「K 个序列当前的头」里挑最小的接上去。 用堆装这 K 个头，poll 最小的，再把那个序列的下一个头补进来，循环即可。17.5 合并 K 个升序链表就是典型。

③ 动态最值：边进边出

数据流场景——元素不是一次性给你，而是一边来一边走，你随时要回答「当前最大值是多少」「中位数多少」。 堆能 O(log n) 维护最值，所以特别适合这种「持续变化、随时查询」的场景（如 347 的频次统计、703 数据流第 K 大等）。

三类用法一句话区分：
  Top K      —— 我只要「最突出的那几个」，其余不要
  多路归并   —— 好几路都排好序了，我要把它们「缝」成一路
  动态最值   —— 数据像水龙头一样流进来，我随时问「现在最值是谁」

17.3数组中的第 K 个最大元素：堆解法（中等，力扣 215）

中等 核心：维护大小为 K 的小顶堆

题意：给你一个整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。 例如 nums = [3,2,1,5,6,4]，k = 2，排序后是 [1,2,3,4,5,6]，第 2 大是 5。注意不要求整体排序，只问第 k 大。

思路推导：为什么是小顶堆，而不是大顶堆？

最直觉的暴力：把数组排序，取倒数第 k 个，O(n log n)。能不能更好？堆可以做到 O(n log k)。

关键问题是：要第 k 大，应该维护什么堆？很多人第一反应是「维护大顶堆，弹出 k-1 次最大的，堆顶就是第 k 大」。这能 work，但要弹出 k-1 次，而且堆里其实装了所有 n 个元素。

更省空间、更优雅的写法是：维护一个大小为 k 的小顶堆。推理如下——

• 我们想保留「目前见过的最大的 k 个数」。这 k 个数里最小的那一个，恰好就是「候选的第 k 大」；
• 所以堆里放「当前最大的 k 个数」，用小顶堆，堆顶就是这 k 个数里最小的，也就是第 k 大的候选；
• 每来一个新数，如果它比堆顶（当前第 k 大候选）还大，说明旧的堆顶不再是前 k 大，把它 poll 掉，新数入堆；
• 遍历结束，堆里正好是最大的 k 个数，堆顶（最小的那个）= 第 k 大。

例子 nums=[3,2,1,5,6,4], k=2，维护大小为 2 的小顶堆：
  看 3：堆空，入 → [3]
  看 2：2<堆顶3，不换（还不够格进前2大）→ [3]   其实要入堆再弹，这里堆未满直接入 [3,2]
  看 1：堆满(2个)，1<堆顶2 → 不入，跳过
  看 5：5>堆顶2 → 弹2入5 → [3,5]
  看 6：6>堆顶3 → 弹3入6 → [5,6]
  看 4：4<堆顶5 → 不入
  结束，堆=[5,6]，堆顶=5 = 第2大 ✓

为什么是小顶而不是大顶？因为我们要找「前 k 大里最小的那个」，小顶堆的堆顶正好暴露这个最小值，方便和后面元素比较淘汰。若用大顶堆，堆顶是最大的，你没法知道「第 k 大」是谁。

参考代码

public int findKthLargest(int[] nums, int k) {
    // 小顶堆：堆顶是当前堆里最小的，也就是「前 k 大里最小的」
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.add(num);            // 先无条件入堆
        if (minHeap.size() > k) {    // 超过 k 个，把最小的（堆顶）扔掉
            minHeap.poll();          // 留下的始终是最大的 k 个数
        }
    }
    return minHeap.peek();           // 堆顶 = 第 k 大
}

复杂度

遍历 n 个元素，每个 add 和 poll 都是 O(log k)（堆大小始终 ≤ k），所以总时间 O(n log k)，空间 O(k)。比排序的 O(n log n) 在 k 远小于 n 时更优。

17.4前 K 个高频元素（中等，力扣 347）

中等 核心：哈希计数 + 按频次排序的堆

题意：给你一个整数数组 nums 和一个整数 k，返回出现频率前 k 高的元素。 例如 nums = [1,1,1,2,2,3]，k = 2，频次是 1→3 次、2→2 次、3→1 次，前 2 高频是 [1,2]（顺序不限）。

思路推导：两步拆开想

这道题其实是两个子问题的组合，拆开反而简单：

• 第一步：统计频次。谁出现了几次？用哈希表 HashMap<Integer, Integer> 扫一遍数组，key 是数、value 是次数。O(n)。
• 第二步：从「频次」里找前 k 大。这不就是 17.3 的「第 k 大」吗？只不过比较的不是数字大小，而是频次大小。

所以做法：把每个「数+频次」塞进一个大小为 k 的小顶堆，比较器按频次（不是按数）比。堆满就弹频次最小的，最后堆里就是前 k 高频。

参考代码

public int[] topKFrequent(int[] nums, int k) {
    // 第一步：哈希计数
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    // 第二步：大小为 k 的小顶堆，按「频次」比较
    // 堆里放 int[]{数值, 频次}，比较器比频次
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(
        (a, b) -> Integer.compare(a[1], b[1])   // 频次小的在堆顶
    );
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        minHeap.add(new int[]{e.getKey(), e.getValue()});
        if (minHeap.size() > k) {
            minHeap.poll();   // 弹掉频次最小的，留下前 k 高频
        }
    }
    // 取出结果
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = minHeap.poll()[0];   // 这里顺序无所谓
    }
    return res;
}

复杂度

计数 O(n)；建堆时最多 n 个不同数，每个插入 O(log k)，O(n log k)；总 O(n log k)，空间 O(n+k)。

17.5合并 K 个升序链表（困难，力扣 23）

困难 核心：K 路归并，堆里放各链表的当前头

题意：给你一个含 k 个链表的数组，每个链表都已升序排列，请你把它们合并成一个升序链表并返回其头节点。 例如 lists = [[1,4,5],[1,3,4],[2,6]]，合并后是 [1,1,2,3,4,4,5,6]。

思路推导：从「逐个合并」到「一起合并」

最容易想到的暴力：先合并第 1 和第 2 条成一条，再拿结果和第 3 条合并……这叫顺序合并。 假设每条平均 n 个节点，合并两条是 O(n)；第 i 次合并要扫前面所有已合并的 i·n 个节点，总复杂度约 O(k²·n)，很慢。

优化思路——多路归并（K 路归并）：想象 k 个指针分别指向 k 条链表的头，每一步我们只要在「这 k 个当前头」里挑最小的接上去，然后把那个指针往后挪一位。 「从 k 个数里反复挑最小」正是堆的强项！用一个小顶堆（按节点值比较）装这 k 个当前头：

• 初始：把 k 条链表的头节点（非 null 的）都入堆；
• 循环：poll 出最小的节点接到结果尾巴上；如果该节点还有 next，把它的 next 入堆（补上这一路的新头）；
• 直到堆空，所有节点都接完了。

lists = [[1,4,5],[1,3,4],[2,6]]，堆按节点值小顶：
初始化堆：[1(链1), 1(链2), 2(链3)]   括号标来自哪条
poll 1(链1) → 结果[1]，补链1的next=4 → 堆[1(链2),2(链3),4(链1)]
poll 1(链2) → 结果[1,1]，补链2的next=3 → 堆[2(链3),3(链2),4(链1)]
poll 2(链3) → 结果[1,1,2]，补链3的next=6 → 堆[3,4,6]
poll 3 → 补4(链2) → 堆[4(链1),4(链2),6]
poll 4(链1) → 补5 → 堆[4(链2),5,6]
poll 4(链2) → 补null(不入) → 堆[5,6]
poll 5 → 补null → 堆[6]
poll 6 → 补null → 堆空
结果：[1,1,2,3,4,4,5,6] ✓

每个节点进堆出堆各一次，每次 O(log k)，总 O(n log k)，比 O(k²n) 好太多。注意用 专题 05 学的虚拟头节点（dummy）统一边界。

参考代码

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    // 小顶堆：堆里放节点，按节点值比较谁小谁在堆顶
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        (a, b) -> Integer.compare(a.val, b.val)
    );
    // 1. 把每条链表的头（非 null）入堆
    for (ListNode head : lists) {
        if (head != null) minHeap.add(head);
    }
    ListNode dummy = new ListNode(0);   // 虚拟头，统一边界
    ListNode tail = dummy;
    // 2. 循环取最小，补 next
    while (!minHeap.isEmpty()) {
        ListNode cur = minHeap.poll();  // 当前最小节点
        tail.next = cur;                // 接结果尾巴
        tail = tail.next;
        if (cur.next != null) {         // 这一路还有后续，补进来
            minHeap.add(cur.next);
        }
    }
    return dummy.next;
}

复杂度

共 n 个节点（n 为所有链表节点总数），每个节点入堆出堆 O(log k)，时间 O(n log k)。空间 O(k)（堆里最多 k 个节点）。边界：lists 为空返回 null；某条链表为空要跳过（代码已处理）。

17.6Top K 三种解法对比

「前 K 大/高频」这类题，至少有三种解法都能做，面试时该选哪个？一张表讲清：

选型口诀：
  数据范围小 + 要全列前 k 个  → 桶排序（最快，O(n)）
  只问「第 k 个是谁」         → 快速选择（平均最快）
  通用 / 数据流 / 值域未知     → 堆（最稳，永远能写）

17.7本专题常见坑

17.8自测题