蓝桥杯JavaB组之堆的基础（优先队列实现TopK问题）

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 paringInt(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] } }

✅ 运行结果

[1, 2] 🔹 4. 时间复杂度分析 统计频率：O(n)维护堆（K 大小）：O(n log k)总时间复杂度：O(n log k)（比直接排序 O(n log n) 更优）

---

📖 四、总结 问题数据结构时间复杂度求数据流的中位数最大堆 + 最小堆O(log n) 插入, O(1) 查询前 K 个高频元素哈希表 + 最小堆O(n log k)

---

📖 五、堆的常考点与易错点

✅ 优先队列默认是最小堆，需要 Collections.reverseOrder() 变成最大堆 ✅ Top K 问题需要维护固定大小的最小堆 ✅ 求数据流中位数，需要两个堆相互平衡

---