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）：存储较大的一半数字

操作规则

1. 新元素先插入最大堆，然后把最大堆的最大值插入最小堆（保证 leftHeap <= rightHeap）。
2. 平衡两个堆的大小（最大堆的元素个数最多只能比最小堆多 1）。
3. 求中位数
   • 若元素总数为奇数，中位数 = 最大堆的堆顶元素
   • 若元素总数为偶数，中位数 = （最大堆堆顶 + 最小堆堆顶）/ 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. 解题思路

哈希表 + 最小堆

1. 用 HashMap 统计每个元素的频率
2. 使用大小为 K 的最小堆 PriorityQueue 存储前 K 个高频元素
3. 遍历 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]}
}

✅ 运行结果

[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 问题需要维护固定大小的最小堆
✅ 求数据流中位数，需要两个堆相互平衡

---