堆与优先队列：Top K 与中位数

这一课你将能做到

1. 说清堆的两种形态（小顶堆、大顶堆）以及插入、取顶的复杂度
2. 用大小为 K 的小顶堆解决第 K 大 / 前 K 高频问题，并判断何时用桶排序
3. 用两个堆维护数据流中位数，解释为什么这样能保持平衡

为什么要学

普通队列是先进先出，优先队列（Priority Queue）则是「每次取当前最优先的元素」，底层就是堆。任务调度里高优先级任务先跑、订单超时扫描、Dijkstra 最短路每次取当前最近节点，靠的都是它。

面试中堆的考法非常集中：Top K 系列和数据流中位数。为什么不用排序一把梭？因为「第 K 大」只关心前 K 个，维护一个 K 大小的堆是 O(n log K)，比全排序 O(n log n) 更省；而且面对源源不断到来的数据流，你不可能每来一个数就整体排序，堆却可以增量地 O(log n) 维护。理解堆，就补上了「在线处理」这块思维拼图。

先建立图像

堆是一棵完全二叉树，逻辑是树、物理存储是数组：

小顶堆           数组表示（下标 0 起）：
    1              [1, 3, 2, 7, 9]
   / \            父 i，子 2i+1 / 2i+2
  3   2           子 i，父 (i-1)/2
 / \
7   9

规则：小顶堆的每个父节点 ≤ 子节点，所以堆顶永远是全局最小；大顶堆反之。插入和取顶都通过「上浮 / 下沉」恢复堆序，O(log n)；peek 为 O(1)。

Java 中：

Queue<Integer> minHeap = new PriorityQueue<>();             // 默认小顶堆
Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

跟着做

步骤 1：LeetCode 215「数组中的第 K 个最大元素」（中等）

如 [3,2,1,5,6,4]、K=2，返回 5。

思路：维护一个大小为 K 的小顶堆，遍历数组往里放；堆大小超过 K 就弹出最小的。走完后，堆里是全体最大的 K 个数，堆顶恰好是其中最小的——即第 K 大。

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> heap = new PriorityQueue<>(k);
        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) {
                heap.poll(); // 踢掉最小的，保住最大的 k 个
            }
        }
        return heap.peek();
    }
}

逐点讲：为什么用小顶堆而不是大顶堆？因为要不断淘汰「K 个候选里最小的」，小顶堆的堆顶正好提供它。时间 O(n log K)，空间 O(K)。

补充：LeetCode 215 最优理论解法是快速选择（Quick Select），平均 O(n)，但最坏 O(n²)、实现易出边界问题。面试给堆解稳妥、够用，能口述 Quick Select 作为加分。

步骤 2：LeetCode 347「前 K 个高频元素」（中等）

返回出现频率前 K 高的元素。

两步走：先用 HashMap 统计频次，再按频次维护大小为 K 的小顶堆。

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.merge(x, 1, Integer::sum);
        }
        // 小顶堆按频次排序，堆顶是候选里频次最低的
        Queue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(freq::get));
        for (int key : freq.keySet()) {
            heap.offer(key);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.stream().mapToInt(Integer::intValue).toArray();
    }
}