当前位置：首页 > article >正文

蓝桥杯 Java B 组之堆的基础（优先队列实现 Top K 问题）

article 2025/2/23 22:54:27

Day 6：堆的基础（优先队列实现 Top K 问题）

📖 一、什么是堆（Heap）？

堆（Heap） 是一种特殊的二叉树结构，满足：

最大堆（Max Heap）：父节点 ≥ 子节点
最小堆（Min Heap）：父节点 ≤ 子节点

堆通常用于实现优先队列（Priority Queue），它能够快速找到最大/最小的元素，常用于： ✅ Top K 问题（前 K 大/小的元素）
✅ 数据流中的中位数
✅ 任务调度（如 CPU 任务管理）

Java 的 PriorityQueue 默认是 最小堆，可以用 自定义 Comparator 实现最大堆。

📖 二、练习 1：求数据流中的中位数

🔹 1. 题目描述

假设你有一个不断流入数字的数据流，需要在任意时刻 求出所有已到达数字的中位数。

中位数：排序后，奇数个元素取中间值，偶数个元素取中间两数的平均值。

示例

输入数据流：1, 2, 3, 4, 5
中位数变化：
- 插入 1，当前中位数 = 1
- 插入 2，当前中位数 = (1+2)/2 = 1.5
- 插入 3，当前中位数 = 2
- 插入 4，当前中位数 = (2+3)/2 = 2.5
- 插入 5，当前中位数 = 3

🔹 2. 解题思路

我们可以用 两个堆（Heap） 来维护数据流：

最大堆（leftHeap）：存储较小的一半数字
最小堆（rightHeap）：存储较大的一半数字

操作规则

新元素先插入最大堆，然后把最大堆的最大值插入最小堆（保证 leftHeap <= rightHeap）。
平衡两个堆的大小（最大堆的元素个数最多只能比最小堆多 1）。
求中位数
- 若元素总数为奇数，中位数 = 最大堆的堆顶元素
- 若元素总数为偶数，中位数 = （最大堆堆顶 + 最小堆堆顶）/ 2.0

🔹 3. Java 代码

import java.util.Collections;
import java.util.PriorityQueue;

public class MedianFinder {
    private PriorityQueue<Integer> leftHeap;  // 最大堆（存较小的一半数）
    private PriorityQueue<Integer> rightHeap; // 最小堆（存较大的一半数）

    public MedianFinder() {
        leftHeap = new PriorityQueue<>(Collections.reverseOrder()); // 大顶堆
        rightHeap = new PriorityQueue<>(); // 小顶堆
    }

    public void addNum(int num) {
        leftHeap.offer(num);  // 先加入最大堆
        rightHeap.offer(leftHeap.poll());  // 把最大堆的最大值转移到最小堆

        if (leftHeap.size() < rightHeap.size()) { 
            leftHeap.offer(rightHeap.poll());  // 保持最大堆元素个数 >= 最小堆
        }
    }

    public double findMedian() {
        if (leftHeap.size() > rightHeap.size()) {
            return leftHeap.peek();  // 奇数个元素，返回最大堆堆顶
        } else {
            return (leftHeap.peek() + rightHeap.peek()) / 2.0;  // 偶数个元素，返回两堆堆顶均值
        }
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        int[] nums = {1, 2, 3, 4, 5};

        for (int num : nums) {
            medianFinder.addNum(num);
            System.out.println("当前中位数：" + medianFinder.findMedian());
        }
    }
}

✅ 运行结果

当前中位数：1.0
当前中位数：1.5
当前中位数：2.0
当前中位数：2.5
当前中位数：3.0

🔹 4. 时间复杂度分析

插入元素：O(log n)（插入堆的时间复杂度）
查找中位数：O(1)（直接返回堆顶元素）

📖 三、练习 2：前 K 个高频元素

🔹 1. 题目描述

给定一个整数数组 nums 和一个整数 k，返回出现次数最多的 前 k 个元素。

示例

输入：nums = [1,1,1,2,2,3], k = 2
输出：[1, 2]

🔹 2. 解题思路

哈希表 + 最小堆

用 HashMap 统计每个元素的频率
使用大小为 K 的最小堆 PriorityQueue 存储前 K 个高频元素
遍历 HashMap，维护堆的大小
- 如果堆中元素个数 < K，直接入堆
- 否则，如果当前元素频率比堆顶元素大，弹出堆顶并加入新元素

🔹 3. Java 代码

import java.util.*;

public class TopKFrequentElements {
    public static int[] topKFrequent(int[] nums, int k) {
        // 统计频率
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 最小堆，按频率排序（堆顶存最小频率）
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

        // 遍历 HashMap，将前 K 个高频元素存入堆
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();  // 维护堆的大小不超过 K
            }
        }

        // 取出堆中的元素
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll().getKey();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        System.out.println(Arrays.toString(topKFrequent(nums, k)));  // 输出：[1, 2]
    }
}

✅ 运行结果