堆与 Top K 模板：前 K、动态最值、优先级问题的标准写法#

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 固定容量 k 的小顶堆

        for (int num : nums) { // 扫描所有元素
            if (minHeap.size() < k) { // 堆未满，直接入堆
                minHeap.offer(num);
            } else if (num > minHeap.peek()) { // 仅当当前元素更大时才更新 TopK
                minHeap.poll(); // 移除 TopK 中最小值
                minHeap.offer(num); // 加入更大元素
            }
        }

        return minHeap.peek(); // 堆顶就是最终第 k 大
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>(); // 统计每个数字出现频次
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1); // 频次 +1
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (a, b) -> count.get(a) - count.get(b) // 频次小的优先出堆，便于维护“频次最高的 k 个”
        );

        for (int num : count.keySet()) { // 遍历去重后的数字集合
            if (minHeap.size() < k) { // 堆未满先放入
                minHeap.offer(num);
            } else if (count.get(num) > count.get(minHeap.peek())) { // 当前数字频次更高，替换堆顶
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        int[] answer = new int[k]; // 输出数组
        for (int index = k - 1; index >= 0; index--) { // 逆序填充，让高频元素在前（可选）
            answer[index] = minHeap.poll(); // 依次弹出堆中元素
        }

        return answer; // 返回前 k 个高频元素
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> a.val - b.val // 按节点值从小到大排列
        );

        for (ListNode node : lists) { // 先把每条链表的头节点入堆
            if (node != null) { // 过滤空链表
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0); // 虚拟头节点，简化拼接逻辑
        ListNode tail = dummy; // 已合并链表的尾指针

        while (!minHeap.isEmpty()) { // 每次弹出当前最小节点
            ListNode current = minHeap.poll(); // 该节点应接到结果链表末尾
            tail.next = current;
            tail = tail.next;

            if (current.next != null) { // 将被弹出节点所在链表的下一个节点继续入堆
                minHeap.offer(current.next);
            }
        }

        return dummy.next; // 返回合并后链表头
    }
}

class MedianFinder {
    private PriorityQueue<Integer> smallerHalf; // 大顶堆：保存较小的一半数据，堆顶是这半中的最大值
    private PriorityQueue<Integer> largerHalf; // 小顶堆：保存较大的一半数据，堆顶是这半中的最小值

    public MedianFinder() {
        smallerHalf = new PriorityQueue<>((a, b) -> b - a); // 初始化大顶堆
        largerHalf = new PriorityQueue<>(); // 初始化小顶堆
    }

    public void addNum(int num) {
        if (smallerHalf.isEmpty() || num <= smallerHalf.peek()) { // 新数更小，先放入左半边
            smallerHalf.offer(num);
        } else { // 新数更大，放入右半边
            largerHalf.offer(num);
        }

        if (smallerHalf.size() > largerHalf.size() + 1) { // 左边过多：把左边最大值移动到右边
            largerHalf.offer(smallerHalf.poll());
        } else if (largerHalf.size() > smallerHalf.size()) { // 右边过多：把右边最小值移动到左边
            smallerHalf.offer(largerHalf.poll());
        }
    }

    public double findMedian() {
        if (smallerHalf.size() > largerHalf.size()) { // 总数为奇数时，左边多一个
            return smallerHalf.peek(); // 中位数就是左堆堆顶
        }
        return (smallerHalf.peek() + largerHalf.peek()) / 2.0; // 总数为偶数时，取两堆顶平均
    }
}