堆与优先队列：原理与核心工程场景

堆的基本概念

堆（二叉堆）是完全二叉树，满足：

• 最大堆：父节点 ≥ 子节点
• 最小堆：父节点 ≤ 子节点

Java 中 PriorityQueue 默认是最小堆。

// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 或
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// 常用操作
pq.offer(x);       // 插入，O(log n)
pq.poll();         // 取出堆顶，O(log n)
pq.peek();         // 查看堆顶，O(1)
pq.size();
pq.isEmpty();

Top K 问题

最小的 K 个数 / 数组中第 K 大元素（LeetCode 215）

最大堆法（维护大小为 K 的最小堆）：

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int x : nums) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll();  // 弹出最小的
    }
    return minHeap.peek();  // 堆顶就是第 k 大
}

快速选择法 O(n) 平均（见排序章节）。

前 K 个高频元素（LeetCode 347）

int[] topKFrequent(int[] nums, int k) {
    // 统计频率
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    // 最小堆，按频率排序，只保留 k 个
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for (var e : freq.entrySet()) {
        minHeap.offer(new int[]{e.getKey(), e.getValue()});
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.stream().mapToInt(a -> a[0]).toArray();
}

最接近原点的 K 个点（LeetCode 973）

int[][] kClosest(int[][] points, int k) {
    // 最大堆（保留距离最小的 k 个）
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1])
    );
    for (int[] p : points) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) maxHeap.poll();
    }
    return maxHeap.toArray(new int[0][]);
}

数据流中的中位数（LeetCode 295）

核心思路：用一个最大堆存较小的一半，一个最小堆存较大的一半，保持大小之差不超过 1。

class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // 最大堆
    PriorityQueue<Integer> hi = new PriorityQueue<>();                            // 最小堆

    void addNum(int num) {
        lo.offer(num);                   // 先加入最大堆
        hi.offer(lo.poll());             // 最大堆堆顶（最大）移入最小堆
        if (lo.size() < hi.size())       // 保持 lo.size >= hi.size
            lo.offer(hi.poll());
    }

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

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

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode node : lists)
        if (node != null) pq.offer(node);
    
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        ListNode min = pq.poll();
        cur.next = min;
        cur = cur.next;
        if (min.next != null) pq.offer(min.next);   // 当前链表下一个节点入堆
    }
    return dummy.next;
}

时间复杂度：O(N log k)，N 是所有节点总数，k 是链表数目。

滑动窗口最大值（LeetCode 239）

单调双端队列（不是堆，但同类问题）：见"单调栈"章节。
堆法（惰性删除）：

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    // 最大堆，存 [值, 下标]
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    for (int i = 0; i < k; i++) maxHeap.offer(new int[]{nums[i], i});
    res[0] = maxHeap.peek()[0];
    for (int i = k; i < n; i++) {
        maxHeap.offer(new int[]{nums[i], i});
        while (maxHeap.peek()[1] <= i - k) maxHeap.poll();  // 惰性删除窗口外元素
        res[i - k + 1] = maxHeap.peek()[0];
    }
    return res;
}

手写最小堆（架构必备）

class MinHeap {
    int[] arr;
    int size;
    MinHeap(int capacity) { arr = new int[capacity]; }
    
    void push(int val) {
        arr[size++] = val;
        siftUp(size - 1);
    }
    
    int pop() {
        int top = arr[0];
        arr[0] = arr[--size];
        siftDown(0);
        return top;
    }
    
    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (arr[parent] <= arr[i]) break;
            swap(i, parent);
            i = parent;
        }
    }
    
    void siftDown(int i) {
        while (2 * i + 1 < size) {
            int j = 2 * i + 1;  // 左子节点
            if (j + 1 < size && arr[j + 1] < arr[j]) j++;  // 更小的子节点
            if (arr[i] <= arr[j]) break;
            swap(i, j);
            i = j;
        }
    }
    
    void swap(int a, int b) {
        int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp;
    }
}

总结