一、堆与优先队列：从底层到实战

堆这个数据结构，说实话，刚学的时候我觉得它挺「别扭」的。明明是个数组，非要想象成完全二叉树。但后来在项目中处理实时排名、TopK 问题时，我才发现——堆是真的香。

我个人习惯把堆理解为「一种能快速找到最值的数据结构」。它不关心中间元素长什么样，只保证堆顶是最大或最小。这种「偏科」的特性，恰恰是它高效的原因。

1.1 堆的两种形态

类型	堆顶元素	父子关系	典型应用
大顶堆	最大值	父节点 ≥ 子节点	求前 K 小
小顶堆	最小值	父节点 ≤ 子节点	求前 K 大

你想想看，如果我们要找前 K 个最大的元素，用小顶堆是不是很反直觉？但恰恰是它——堆顶是当前最小的候选，新元素比堆顶大就替换掉，这样堆里始终保留着最大的 K 个。

1.2 堆的构建：从数组到堆

堆的构建有两种方式：

• 逐个插入：O(n log n)，适合数据动态到达的场景
• 原地建堆（Floyd 算法）：O(n)，从最后一个非叶子节点开始下沉

我记得第一次手写堆排序时，就是栽在了「下沉」和「上浮」的边界条件上。这里我直接给出最常用的原地建堆代码：

// 构建大顶堆
void buildMaxHeap(int[] arr, int n) {
    // 从最后一个非叶子节点开始下沉
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }
}

void siftDown(int[] arr, int i, int n) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        swap(arr, i, largest);
        siftDown(arr, largest, n);  // 继续下沉
    }
}

1.3 堆排序：原地排序的经典

堆排序分两步：建堆 + 排序。排序阶段就是不断把堆顶（最大值）换到末尾，然后对剩余部分重新调整。

void heapSort(int[] arr) {
    int n = arr.length;
    buildMaxHeap(arr, n);  // 第一步：建堆

    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);   // 堆顶放到末尾
        siftDown(arr, 0, i); // 调整剩余部分
    }
}

时间复杂度稳定 O(n log n)，空间复杂度 O(1)。但说实话，实际项目中我很少用堆排序——快速排序的平均性能更好。堆排序最大的价值，是它衍生出的优先队列思想。

1.4 经典例题一：前 K 个高频元素

这道题是 LeetCode 347。题目给你一个数组，要你返回出现频率最高的 K 个元素。

我的解法思路：先用哈希表统计频率，然后用小顶堆维护 Top K。

public int[] topKFrequent(int[] nums, int k) {
    // 1. 统计频率
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // 2. 小顶堆，按频率排序
    PriorityQueue<Map.Entry<Integer, Integer>> heap =
        new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        heap.offer(entry);
        if (heap.size() > k) {
            heap.poll();  // 移除频率最小的
        }
    }

    // 3. 取出结果
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = heap.poll().getKey();
    }
    return res;
}

1.5 经典例题二：数据流的中位数

这道题是 LeetCode 295。数据不断流入，要求随时能获取当前所有数的中位数。

我当时的直觉是：能不能用两个堆？一个大顶堆放较小的一半，一个小顶堆放较大的一半。这样中位数就是两个堆顶的平均值（或其中一个）。

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 存较小的一半
    private PriorityQueue<Integer> minHeap; // 存较大的一半

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 先放入大顶堆
        maxHeap.offer(num);
        // 平衡：保证大顶堆所有元素 ≤ 小顶堆所有元素
        minHeap.offer(maxHeap.poll());

        // 保持大顶堆大小 ≥ 小顶堆
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

1.6 知识体系总览

下面这张图是我自己总结的堆与优先队列的知识脉络，你可以对照着复习：

1.7 避坑指南与经验总结

• 堆的大小控制：用优先队列做 TopK 时，一定要限制堆的大小。否则堆退化成了排序，性能优势就没了。
• 比较器方向：Java 的 PriorityQueue 默认是小顶堆。想要大顶堆，记得传 (a,b) -> b-a。我刚开始写反过好几次。
• 数据流场景：如果数据量极大（比如上亿），堆的 O(log k) 插入依然很快。但要注意内存——堆本身要存 K 个元素，K 不能太大。

堆与优先队列的核心就这些。说白了，它就是「用空间换时间」的典型——用 O(n) 的空间，换来 O(log n) 的插入和 O(1) 的取最值。这个性价比，在算法设计里是非常划算的。

---