一、堆基础知识

1. 堆概念

  堆是一种特殊的树形数据结构。根据根节点的值与子节点的值的大小关系，堆又分为最大堆和最小堆。在最大堆中，每个节点的值总是大于或等于其任意子节点的值，因此最大堆的根节点就是整个堆的最大值。在最小堆中，每个节点的值总是小于或等于其任意子节点的值，因此最小堆的根节点就是整个堆的最小值。
  堆通常用完全二叉树实现。在完全二叉树中，除最低层之外，其他层都被节点填满，最低层尽可能从左到右插入节点。

二、知识扩展 & 练习

1. 堆的应用

知识扩展

  堆最大的特点是最大值或最小值位于堆的顶部，只需要 O (1)的时间就可以求出一个数据集合中的最大值或最小值，同时在堆中添加或删除元素的时间复杂度都是 O(logn)，因此综合来看堆是一个比较高效的数据结构。
  堆经常用来求取一个数据集合中值最大或最小的 k 个元素。通常，最小堆用来求取数据集合中 k 个值最大的元素，最大堆用来求取数据集 合中 k 个值最小的元素。
  Java 中可以常借助 PriorityQueue 实现最小堆和最大堆；最小堆 new PriorityQueue()；最大堆 new PriorityQueue((x, y) -> y - x)。

题目练习

Ⅰ：数据流的第 k 大数字
题目描述

  请设计一个类型 KthLargest，它每次从一个数据流中读取一个数字，并得出数据流已经读取的数字中第 k(k ≥ 1) 大的数字。该类型的构造函数有两个参数：一个是整数 k，另一个是包含数据流中最开始数字的整数数组 nums (假设数组 nums 的长度大于 k)。该类型还有一个函数 add，用来添加数据流中的新数字并返回数据流中已经读取的数字的第 k 大数字。

题目分析

难度： ⭐⭐🐇🐇🐇
思路： 获取第 k 大的元素时，如果能按从大到小的顺序将 k 个元素放入某个集合，而这个集合中最小的值就是所求的元素。后续加入新的值时，拿最小的值和其进行比较，如果比最小值大，最小值移除，而新的值放入。这样需要维护一个动态的递增数据结构，使用最小堆的数据结构比较容易解决，也就是 Java 中的优先队列。

参考代码
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author nepakina
 */
public class KthLargest {

    private final int size;
    private final Queue<Integer> queue;

    public KthLargest(int k, int[] nums) {
        size = k;
        queue = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    public Integer add(int val) {
        if (queue.size() >= size) {
            Integer peek = queue.peek();
            if (peek == null || val > queue.peek()) {
                queue.poll();
                queue.add(val);
            }
        } else {
            queue.add(val);
        }
        return queue.peek();
    }
}
Tips：2025-05-29
Ⅱ：出现频率最高的 k 个数字
题目描述

  请找出数组中出现频率最高的 k 个数字。例如，当 k 等于 2 时，输入数组 [1, 2, 2, 1, 3, 1]，由于数字 1 出现了 3 次，数字 2 出现了 2 次，数字 3 出现了 1 次，因此出现频率最高的 2 个数字是 1 和 2。

题目分析

难度： ⭐⭐🐇🐇🐇
思路： 按出现次数对数组元素分类，以出现次数为比较依据，将其按最小堆处理。遍历完整个数组后，将最小堆的所有元素即为所求。

参考代码
public int[] findHighFrequencyNums(int nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums; i++) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }
    Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>();
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (queue.size() >= k) {
            Map.Entry<Integer, Integer> peek = queue.peek();
            // 出现次数最少的元素比新元素还少时，该元素移除，添加新元素
            if (peek == null || entry.getValue() > peek.getValue()) {
                queue.poll();
                queue.offer(entry);
            }
        } else {
            queue.offer(entry);
        }
    }
    int[] res = new int[queue.size()];
    for (int i = 0; i < queue.size(); i++) {
        res[i] = queue.poll().getKey();
    }
    return res;
}
Tips：2025-05-29
Ⅲ：和最小的 k 个数对
题目描述

  给定两个递增排序的整数数组，从两个数组中各取一个数字 u 和 v 组成一个数对 (u, v)，请找出和最小的 k 个数对。例如，输入两个数组 [1, 5, 13, 21] 和 [2, 4, 9, 15]，和最小的 3 个数对为 (1, 2)、(1, 4) 和 (2, 5)。

题目分析

难度： ⭐⭐🐇🐇🐇
思路：
  首先要对元素进行排列组合，组合后的元素作为一个整体当作堆的元素。这里可以借助数组来实现，定义一个大小为 2 的数组存储两个值。在比较时，要以两个值的和来做比较。由于求的是最小的 k 个元素，最大堆比较合适。
  由于原数组是有序的，所以在整个过程中，可以发现存在诸多的重复比较，即假设 (5, 9) 不属于最小的 k 个元素中的值，那么 (5, 15) 则不需要再进行判断处理。同时如果 A 数组已经取了 k 个元素，那么后续元素也没必要进行遍历了，B 数组同理。所以由于 A、B 是有序的集合，可以在排列组合时将堆元素的处理也一并进行处理，同时基于堆增加一些遍历限制规避不必要的遍历。
  整个问题还可以用最小堆解决，我们使用最小堆直接存放最小的元素组。如何存放最小元素组呢？由于整数数组是有序的，我们可以利用双指针和滑块的相似特性。
  首先定义两个指针 i、j，i 代表 A 数组的表里下标，j 代表 B 数组，然后按照排列组合将数组 A 中分别和数组 B 的第一个元素组成的 k 个组合放入最小堆中（如果不足 k 个，则是 A.length() 个组合）；由于两个数组是有序的，所以从 (A[0], B[0]) 开始下一个较小的元素应该是当前堆顶元素 (A[i], B[j]) 移动一格后的新组合，即 (A[i + 1], B[j])、(A[i], B[j + 1]) 其中之一，此时将比较小的组合放入堆中，并将其在两个数组中的下标赋予此时的 i、j；重复这个过程，直到找到 k 个这样的元素。

参考代码
// 方案一：常规遍历最大堆处理
public List<int[]> findMinNums(int[] numsA, int[] numsB, int k) {
    List<int[]> list = new ArrayList<>();
    // 按要求进行随机组合
    for (int i = 0; i < numsA.length; i++) {
        int numA = numsA[i];
        for (int j = i + 1; j < numsB.length; j++) {
            int numB = numsB[i];
            int[] arr = numA <= numB ? new int[]{numA, numB} : new int[]{numB, numA};
            list.add(arr);
        }
    }
    Queue<int[]> queue = new PriorityQueue<>((x, y) -> y[0] + y[1] - x[0] + x[1]);
    for (int[] arr : list) {
        if (queue.size() >= k) {
            int[] peek = queue.peek();
            // 比较基础变更为了两个值的和，同时采用最大堆处理
            if (peek == null || arr[0] + arr[1] < peek[0] + peek[1]) {
                queue.poll();
                queue.offer(new int[]{arr[0], arr[1]});
            }
        } else {
            queue.offer(new int[]{arr[0], arr[1]});
        }
    }
    List<int[]> res = new ArrayList<>();
    for (int i = 0; i < queue.size(); i++) {
        res.add(queue.poll());
    }
    return res;
}
// 方案一优化：略
// 方案二：最小堆
Tips：2025-05-29

三、章节小结

  堆又可以分成最大堆和最小堆。在最大堆中最大值总是位于堆顶，在最小堆中最小值总是位于堆顶。因此，在堆中只需要 O(1) 的时间就能得到堆中的最大值或最小值。
  堆经常用来解决在数据集合中找出 k 个最大值或最小值相关的问题。通常用最大堆找出数据集合中的 k 个最小值，用最小堆找出数据集合中的 k 个最大值。
  Java 的库中提供了类型 PriorityQueue，虽然该类型实现了接口 Queue，但它是堆而不是队列。PriorityQueue 的构造函数能传入不同的比较规则，从而创建最大堆或最小堆。
  虽然章节大多定义难度为⭐⭐🐇🐇🐇，但实际上在使用堆结构后，都只是对该结构的简单应用。