当前位置: 首页> 财经> 产业 > 莆田专业网站制作_凡科快图免费版商用_营销型企业网站制作_微博搜索引擎优化

莆田专业网站制作_凡科快图免费版商用_营销型企业网站制作_微博搜索引擎优化

时间:2025/7/14 20:21:32来源:https://blog.csdn.net/2301_77523055/article/details/145739855 浏览次数:0次
莆田专业网站制作_凡科快图免费版商用_营销型企业网站制作_微博搜索引擎优化

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


关键字:莆田专业网站制作_凡科快图免费版商用_营销型企业网站制作_微博搜索引擎优化

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: