堆的核心概念

堆（Heap）是一种特殊的完全二叉树结构，通常用数组实现。Java 中的 PriorityQueue 默认是小顶堆（堆顶元素最小），通过传入 Comparator.reverseOrder() 可变为大顶堆。

堆的核心操作时间复杂度：

• 插入（offer / add）：O(log n)
• 删除堆顶（poll）：O(log n)
• 获取堆顶（peek）：O(1)

堆在算法题中的核心价值在于 动态维护一组元素中的极值，特别适合 TopK 问题（求第 K 大/小、前 K 个高频元素等）。当数据量极大且无法全量排序时，堆能以 O(n log K) 的复杂度完成筛选，远优于全排序的 O(n log n)。

LeetCode 热门 100 题中，有三道题与堆密切相关：215. 数组中的第K个最大元素（堆求 TopK）、347. 前 K 个高频元素（哈希表统计 + 堆筛选）、395. 至少有K个重复字符的最长子串（堆作为辅助工具，配合分治解决）。前两题是堆的经典应用，第三题展示了堆在复杂场景中的灵活运用。

1. 数组中的第K个最大元素（LeetCode 215）

题目：给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。注意是排序后的第 k 个最大元素，而非第 k 个不同元素。

暴力法：对数组排序后取第 n - k 个元素，时间复杂度 O(n log n)。

堆优化思路：维护一个大小为 k 的小顶堆。遍历数组，将元素加入堆中，当堆大小超过 k 时弹出堆顶（最小的元素）。遍历结束后，堆顶就是第 k 大的元素。因为堆中保留的是当前遍历过的所有元素中 最大的 k 个，堆顶是这 k 个中最小的，即全局第 k 大。

具体步骤：

• 创建一个小顶堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>()。
• 遍历数组每个元素 num：
  • minHeap.offer(num)。
  • 如果 minHeap.size() > k，执行 minHeap.poll()。
• 返回 minHeap.peek()。

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

复杂度：时间复杂度 O(n log k)，空间复杂度 O(k)。

关键点：使用小顶堆而非大顶堆，因为我们要保留最大的 k 个数，堆顶是这 k 个数中最小的，便于淘汰。当 k 接近 n 时，堆方案不如直接排序，但 k 较小时优势明显。

2. 前K个高频元素（LeetCode 347）

题目：给定整数数组 nums 和整数 k，返回出现频率前 k 高的元素。可以按任意顺序返回答案。

暴力法：统计每个元素的频率，然后按频率排序取前 k 个，时间复杂度 O(n log n)。

堆优化思路：先用哈希表统计每个元素的频率，然后用大小为 k 的小顶堆存储 (频率, 元素) 对。遍历哈希表，将键值对加入堆中，当堆大小超过 k 时弹出频率最小的元素。遍历结束后，堆中剩下的就是频率最高的 k 个元素。

具体步骤：

• 用 HashMap<Integer, Integer> 统计每个元素的出现次数。
• 创建小顶堆 PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]))，存储 [频率, 元素]。
• 遍历哈希表的 entrySet：
  • minHeap.offer(new int[]{freq, val})。
  • 如果 minHeap.size() > k，执行 minHeap.poll()。
• 从堆中取出所有元素，返回结果数组。

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        minHeap.offer(new int[]{entry.getValue(), entry.getKey()});
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll()[1];
    }
    return result;
}

复杂度：时间复杂度 O(n log k)，空间复杂度 O(n)。

关键点：堆中存储的是 [频率, 元素]，比较器按频率排序。这里 k 是频率最高的前 k 个元素，与第 215 题的 k 含义一致，都是"保留最大的 k 个"。

3. 至少有K个重复字符的最长子串（LeetCode 395）

题目：给定字符串 s 和整数 k，找出 s 中的最长子串，要求该子串中 每个字符 的出现次数都不少于 k。返回该子串的长度。

暴力法：枚举所有子串，统计每个字符频次并检查是否都 >= k，时间复杂度 O(n³) 或 O(n²)。

堆辅助的分治思路：这题最经典的解法是分治，但堆可以作为一个辅助工具来优化某些步骤。

核心观察：如果某个字符 c 在整个字符串中的总出现次数小于 k，那么任何包含 c 的子串都不可能满足条件。因此，可以 以 c 为分割点 将字符串切分成若干段，递归处理每一段。

堆的辅助作用：在分治过程中，需要快速找出当前段中所有出现次数 < k 的字符作为分割点。可以用一个最小堆存储 (出现次数, 字符)，堆顶就是出现次数最少的字符，如果堆顶次数 >= k，则当前段已经满足条件，直接返回段长；否则弹出该字符作为分割点进行递归。

具体步骤：

• 统计当前段 [left, right] 内每个字符的出现次数。
• 将出现次数 < k 的字符放入小顶堆（按次数排序）。
• 如果堆为空，说明当前段所有字符出现次数都 >= k，返回段长 right - left + 1。
• 否则，取出堆顶字符 splitChar，以该字符为分割点，将段分成若干子段，递归处理每个子段，取最大值。

public int longestSubstring(String s, int k) {
    return dfs(s, 0, s.length() - 1, k);
}

private int dfs(String s, int left, int right, int k) {
    if (left > right) return 0;
    // 统计当前段频次
    int[] freq = new int[26];
    for (int i = left; i <= right; i++) {
        freq[s.charAt(i) - 'a']++;
    }
    // 小顶堆存储出现次数 < k 的字符
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0 && freq[i] < k) {
            minHeap.offer(new int[]{i, freq[i]});
        }
    }
    if (minHeap.isEmpty()) {
        return right - left + 1;
    }
    int splitChar = minHeap.poll()[0];
    int maxLen = 0;
    int start = left;
    for (int i = left; i <= right; i++) {
        if (s.charAt(i) - 'a' == splitChar) {
            maxLen = Math.max(maxLen, dfs(s, start, i - 1, k));
            start = i + 1;
        }
    }
    maxLen = Math.max(maxLen, dfs(s, start, right, k));
    return maxLen;
}

复杂度：最坏情况下 O(n²)（如每次只分割一个字符），平均情况优于暴力。堆的引入使得寻找分割字符更高效（O(26 log 26) 常数级），但整体复杂度仍由递归决定。

关键点：这题的堆用法与传统 TopK 不同——堆在这里是 辅助筛选工具，用于快速定位"不合格"的字符作为分割点。如果不用堆，每次遍历 26 个字母也能达到同样效果（因为字符集只有 26 个），但堆的思路更具通用性，当字符集更大时优势更明显。

三题对比与启发

共同本质：堆在这三题中的核心价值都是 快速获取当前数据集中的极值（最小值或频率最低值）。无论是保留 TopK 时的"淘汰最小值"，还是分治时的"找到最少出现的字符"，堆都提供了 O(log n) 的极值访问能力。

不同侧重：

• 第 215 题：堆作为 唯一数据结构，完成 TopK 筛选。
• 第 347 题：堆与哈希表 配合，先统计再筛选。
• 第 395 题：堆作为 辅助工具，嵌入分治框架中加速决策。

总结：堆模块的核心心法

堆的本质是"动态极值容器"。当问题涉及"保留最大的 K 个"、“淘汰最小的”、“反复取当前最值"等场景时，堆往往是 O(n log K) 最优解的不二之选。

应用堆的通用思考路径：

1. 识别问题是否需要 维护一组数据的极值。
2. 确定堆中存储的元素类型（数值、频率、配对对象等）。
3. 确定堆的类型——小顶堆用于保留最大的 K 个（淘汰最小的），大顶堆用于保留最小的 K 个（淘汰最大的）。
4. 注意堆的大小控制：通常保持堆大小不超过 K，每次插入后检查并弹出。