跳到主要内容

堆与优先队列

问题​

Java 中堆（PriorityQueue）相关的常见算法题有哪些？

答案​

Java 中堆通过 PriorityQueue 实现，默认小顶堆。

前 K 个高频元素（LeetCode 347）​

小顶堆维护 TopK
public int[] topKFrequent(int[] nums, int k) {
    // 1. 统计频次
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) freq.merge(num, 1, Integer::sum);
    
    // 2. 小顶堆，按频次排序，堆大小保持 k
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for (var entry : freq.entrySet()) {
        minHeap.offer(new int[]{entry.getKey(), entry.getValue()});
        if (minHeap.size() > k) minHeap.poll();  // 弹出最小的
    }
    
    // 3. 堆中剩余 k 个就是最高频的
    int[] result = new int[k];
    for (int i = 0; i < k; i++) result[i] = minHeap.poll()[0];
    return result;
}

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

小顶堆 O(n log k)
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.peek();  // 堆顶就是第 K 大
}

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

最小堆多路归并
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode head : lists) {
        if (head != null) minHeap.offer(head);
    }
    
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        cur.next = node;
        cur = cur.next;
        if (node.next != null) minHeap.offer(node.next);
    }
    return dummy.next;
}

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

大顶堆 + 小顶堆
class MedianFinder {
    // 大顶堆存较小的一半，小顶堆存较大的一半
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());  // 平衡：先入大顶堆，再把最大的给小顶堆
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());  // 保持大顶堆 >= 小顶堆
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) return maxHeap.peek();
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}
TopK 问题总结
  • 求最大的 K 个 → 小顶堆，堆大小 K，时间 O(nlog⁡k)O(n \log k)
  • 求最小的 K 个 → 大顶堆，堆大小 K
  • 求中位数 → 大顶堆 + 小顶堆对半维护

常见面试问题​

Q1: 为什么求 TopK 大用小顶堆而不是大顶堆？​

答案：

小顶堆堆顶是最小值，始终淘汰当前 K 个中最小的，最终留下最大的 K 个。大顶堆需要把所有元素入堆才能取 TopK，空间 O(n)O(n)；小顶堆只需 O(k)O(k) 空间。

Q2: PriorityQueue 的底层实现？​

答案：

基于数组实现的二叉堆。offer 和 poll 时间 O(log⁡n)O(\log n)，peek 时间 O(1)O(1)。详见 Queue 与 Deque。

Q3: 堆排序 vs PriorityQueue？​

答案：

堆排序是原地排序 O(nlog⁡n)O(n \log n)、O(1)O(1) 空间；PriorityQueue 是动态数据结构，支持持续插入和删除。TopK 问题用 PriorityQueue 更方便。

相关链接​