堆与优先队列进阶：Top-K 与流式计算

堆（优先队列）的使用时机

• Top K 问题：维护大小为 K 的堆
• 流式数据的中位数：双堆（大根堆 + 小根堆）
• K 路归并：多个有序序列合并
• 任务调度：按优先级出队

Top K 模式

数据流中的第 K 大元素（LeetCode 703）

小根堆维护大小为 k 的堆：堆顶就是第 k 大：

class KthLargest {
    private PriorityQueue<Integer> pq = new PriorityQueue<>();  // 小根堆
    private int k;

    KthLargest(int k, int[] nums) {
        this.k = k;
        for (int n : nums) add(n);
    }

    int add(int val) {
        pq.offer(val);
        if (pq.size() > k) pq.poll();  // 超出 k 个时弹出最小的
        return pq.peek();              // 堆顶 = 第 k 大
    }
}

技巧：保留「最大的 k 个」用小根堆，堆顶是 k 个中最小的（即第 k 大）。

查找和最小的 K 对数字（LeetCode 373）

K 路归并思路：初始把每行（nums1[i] + nums2[0]）放入堆，每次弹出最小后加入下一个：

List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<List<Integer>> res = new ArrayList<>();
    // [sum, i, j]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));

    for (int i = 0; i < Math.min(nums1.length, k); i++) {
        pq.offer(new int[]{nums1[i] + nums2[0], i, 0});
    }

    while (!pq.isEmpty() && res.size() < k) {
        int[] cur = pq.poll();
        int i = cur[1], j = cur[2];
        res.add(Arrays.asList(nums1[i], nums2[j]));
        if (j + 1 < nums2.length) {
            pq.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
        }
    }
    return res;
}

数据流的中位数（LeetCode 295）

用两个堆：

• 大根堆（maxHeap）保存较小的一半
• 小根堆（minHeap）保存较大的一半

维持大根堆大小 ≥ 小根堆（差值不超过 1）：

class MedianFinder {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 小的一半
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();                            // 大的一半

    void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());  // 先加大根堆，再把最大的移到小根堆
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll()); // 保持大根堆不少于小根堆
        }
    }

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

滑动窗口最大值（LeetCode 239）

用单调递减双端队列（deque）维护窗口内最大值，比堆更高效（O(n) vs O(n log n)）：

int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();  // 存下标，单调递减
    int[] res = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // 移除超出窗口的下标
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
        // 维护单调递减：移除所有比当前值小的
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
        dq.offerLast(i);
        // 窗口满了开始记录结果
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

合并 K 个升序链表（LeetCode 23）

K 路归并经典题：将每个链表头节点入堆，每次弹出最小后加入下一个节点：

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode head : lists) {
        if (head != null) pq.offer(head);
    }

    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        cur.next = node;
        cur = cur.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

选型总结