跳到主要内容

堆算法练习

堆（Heap）通常通过优先队列（Priority Queue）来实现。考察热题主要涉及 Top K 问题和动态维护中位数。

215. 数组中的第K个最大元素 (Kth Largest Element in an Array)​

题目描述​

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

解题思路​

利用最小堆维护 k 个最大的数。当堆满后，如果新数比堆顶大，弹堆顶推入新数。最后堆顶即为答案。

Java 代码实现​

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
            if (pq.size() > k) pq.poll();
        }
        return pq.peek();
    }
}

347. 前 K 个高频元素 (Top K Frequent Elements)​

题目描述​

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

解题思路​

  1. 哈希表统计频率。
  2. 使用优先队列（最小堆）维护频率前 k 的元素对。
  3. 也可以利用桶排序的思想将频率转化为索引。

Java 代码实现​

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(new int[]{entry.getKey(), entry.getValue()});
            if (pq.size() > k) pq.poll();
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = pq.poll()[0];
        return res;
    }
}

295. 数据流的中位数 (Find Median from Data Stream)​

题目描述​

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 设计一个支持添加数据并返回中位数的数据结构。

解题思路​

使用两个对冲堆：

  1. 最大堆 left 存放较小的一半元素。
  2. 最小堆 right 存放较大的一半元素。
  3. 始终保证两堆节点数之差不超过 1，且左堆顶小于等于右堆顶。

Java 代码实现​

class MedianFinder {
    private PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
    private PriorityQueue<Integer> right = new PriorityQueue<>();
    public void addNum(int num) {
        if (left.isEmpty() || num <= left.peek()) {
            left.add(num); if (left.size() > right.size() + 1) right.add(left.poll());
        } else {
            right.add(num); if (right.size() > left.size()) left.add(right.poll());
        }
    }
    public double findMedian() {
        if (left.size() == right.size()) return (left.peek() + right.peek()) / 2.0;
        return left.peek();
    }
}