堆与优先队列算法：Top K、中位数与任务调度

“堆与优先队列算法：Top K、中位数与任务调度”这一块，我曾经有一种很典型的错觉：内容看懂了，自己也会了。我真正关掉答案后才发现：我刚学堆时总想把它画成一棵完整的树，写代码才发现真正需要掌握的是数组下标和上浮、下沉的不变量。后来我用画图、手算和最小代码反复验证，才把表面的熟悉变成可以复述的理解。

堆在数据结构篇里已经讲过实现，这篇更关注算法应用。堆的价值不是“把所有元素排好序”，而是用较低成本持续维护当前最大或最小的候选。

堆的应用地图

堆与 Top K 场景选择

图：堆适合动态维护最值，而不是一次性全排序

常见选择：

问题	推荐结构	思路
第 k 大	小顶堆	堆里只保留 k 个最大候选
前 k 个高频元素	小顶堆 / 桶排序	按频次维护候选
数据流中位数	大顶堆 + 小顶堆	左半和右半各维护一个堆
合并 k 个有序链表	小顶堆	每次取当前最小节点
任务调度	优先队列	按优先级或时间排序

Top K：小顶堆保留最大 k 个

求数组第 k 大时，不需要把所有元素排序。维护一个容量为 k 的小顶堆即可。

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

堆中保存的是当前见过的 k 个最大值，堆顶是这 k 个值中最小的，也就是第 k 大。

复杂度是 O(n log k)，当 k 远小于 n 时，比全排序更合适。

前 k 个高频元素

先用哈希表统计频次，再用小顶堆保留频次最高的 k 个元素。

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) {
        freq.put(x, freq.getOrDefault(x, 0) + 1);
    }

    PriorityQueue<int[]> heap = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[1])
    );
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});
        if (heap.size() > k) heap.poll();
    }

    int[] ans = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        ans[i] = heap.poll()[0];
    }
    return ans;
}

如果频次范围明确，也可以使用桶排序，把元素按出现次数放入桶中。

数据流中位数：两个堆平衡

中位数需要知道左半部分最大值和右半部分最小值。可以用大顶堆维护左半，用小顶堆维护右半。

class MedianFinder {
    PriorityQueue<Integer> small = new PriorityQueue<>(Comparator.reverseOrder());
    PriorityQueue<Integer> large = new PriorityQueue<>();

    void addNum(int num) {
        if (small.isEmpty() || num <= small.peek()) {
            small.offer(num);
        } else {
            large.offer(num);
        }
        if (small.size() > large.size() + 1) {
            large.offer(small.poll());
        } else if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }

    double findMedian() {
        if (small.size() == large.size()) {
            return ((double) small.peek() + large.peek()) / 2;
        }
        return small.peek();
    }
}

两个堆要满足两个不变量：

small 中的元素都不大于 large 中的元素。
两个堆大小差不超过 1。

工程场景

堆在工程里经常用于：

延迟任务队列：按执行时间排序。
告警聚合：优先处理严重等级高的事件。
排行榜候选：维护局部 Top K。
多路归并：合并多个有序来源的数据流。
流式统计：数据不断到来时持续更新结果。

我的分析

如果只是一次性排序，堆排序未必是最舒服的选择；但如果数据是动态到来的，或者只关心前 k 个，堆就非常合适。判断是否用堆，我会看两个关键词：动态、最值。

面试题

求第 k 大为什么用小顶堆，而不是大顶堆？
PriorityQueue 默认是小顶堆还是大顶堆？
两个堆求中位数要维护哪些不变量？
Top K 和排序相比，什么时候更有优势？
堆能不能快速删除任意元素？为什么？