数据流的中位数：用双堆优雅处理动态数据的中位数计算！

大家好，我是忍者算法。今天我们来聊一个非常有趣的题目 - 数据流中的中位数。这个问题看似简单，实则暗藏玄机，需要我们巧妙运用堆这个数据结构来解决。别担心！我会用最直观的方式，带你理解这个精妙的解决方案。

📚 生活中的中位数

想象你是一个体育老师，正在记录学生们的跑步成绩。每当有新的同学完成跑步，你都需要立即知道到目前为止所有成绩的中位数。这就是我们今天要解决的核心问题！

💡 问题是什么

用大白话说：我们要设计一个数据结构，支持两个操作：

1. 添加一个新的数字到我们的数据集中
2. 随时可以获取当前所有数字的中位数

比如说：

// 假设数据流是：[4,5,8,2,3]
addNum(4)    // [4]，中位数是4
addNum(5)    // [4,5]，中位数是4.5
addNum(8)    // [4,5,8]，中位数是5
addNum(2)    // [2,4,5,8]，中位数是4.5
addNum(3)    // [2,3,4,5,8]，中位数是4

🤔 为什么这个问题有趣？

这个问题的挑战在于：

1. 数据是流式输入的，我们不能预先知道所有数字
2. 每次添加新数字后都要能快速得到中位数
3. 数据规模可能很大，我们需要高效的解决方案

🚀 优雅的解决方案

我们可以用两个堆来解决这个问题：

• 一个大顶堆存储较小的一半数字
• 一个小顶堆存储较大的一半数字

class MedianFinder {
    // 大顶堆，存储较小的一半数字
    private PriorityQueue<Integer> smallerHalf;
    // 小顶堆，存储较大的一半数字
    private PriorityQueue<Integer> largerHalf;
    
    public MedianFinder() {
        // 初始化两个堆
        smallerHalf = new PriorityQueue<>((a, b) -> b - a);  // 大顶堆
        largerHalf = new PriorityQueue<>();                  // 小顶堆
    }
    
    public void addNum(int num) {
        // 先把新数字放入大顶堆（较小的一半）
        smallerHalf.offer(num);
        
        // 确保smallerHalf中的最大数不超过largerHalf中的最小数
        if (!smallerHalf.isEmpty() && !largerHalf.isEmpty() && 
            smallerHalf.peek() > largerHalf.peek()) {
            largerHalf.offer(smallerHalf.poll());
        }
        
        // 保持两个堆的大小平衡
        // 允许smallerHalf比largerHalf最多多一个元素
        if (smallerHalf.size() > largerHalf.size() + 1) {
            largerHalf.offer(smallerHalf.poll());
        }
        if (largerHalf.size() > smallerHalf.size()) {
            smallerHalf.offer(largerHalf.poll());
        }
    }
    
    public double findMedian() {
        if (smallerHalf.size() > largerHalf.size()) {
            // 奇数个元素时，中位数就是smallerHalf的堆顶
            return smallerHalf.peek();
        } else {
            // 偶数个元素时，中位数是两个堆顶的平均值
            return (smallerHalf.peek() + largerHalf.peek()) / 2.0;
        }
    }
}

📝 代码是怎么工作的？

让我们用一个具体的例子来看看这个结构是如何工作的：

假设数据流是：[4,5,8,2,3]

1. 添加4：

   • smallerHalf: [4]
   • largerHalf: []
   • 中位数：4

2. 添加5：

   • smallerHalf: [4]
   • largerHalf: [5]
   • 中位数：(4+5)/2 = 4.5

3. 添加8：

   • smallerHalf: [4]
   • largerHalf: [5,8]
   • 平衡后：
     • smallerHalf: [4,5]
     • largerHalf: [8]
   • 中位数：5

依此类推...就像是在玩跷跷板，我们始终保持两边平衡，中位数自然就在中间！

🎯 要注意的关键点

1. 堆的选择

   • 为什么用大顶堆和小顶堆？
   • 这样可以方便地获取中间的数字

2. 平衡的维护

   • 两个堆的大小差不超过1
   • 较小堆的最大值不超过较大堆的最小值

3. 处理偶数和奇数的情况

   • 奇数个数时：中位数是较小堆的堆顶
   • 偶数个数时：中位数是两个堆顶的平均值

💡 生活中的类似场景

这种设计思路在生活中很常见：

1. 考试成绩统计

   • 实时计算班级的中等成绩
   • 新的成绩提交后快速更新

2. 房价中位数

   • 房地产市场的价格中位数
   • 新房源上市后的即时统计

3. 工资中位数

   • 公司薪资水平的中位数
   • 新员工入职后的即时更新

🎨 解决方案的可视化

<svg viewBox="0 0 600 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="600" height="400" fill="#f8f9fa"/>
  
  <!-- 标题 -->
  <text x="300" y="40" font-size="20" fill="#1976d2" text-anchor="middle">双堆结构示意图</text>
  
  <!-- 左边的大顶堆 -->
  <g transform="translate(150,100)">
    <text x="0" y="-20" text-anchor="middle" fill="#2196f3">较小的一半(大顶堆)</text>
    <path d="M 0 0 L -60 60 L 60 60 Z" fill="none" stroke="#2196f3" stroke-width="2"/>
    <circle cx="0" cy="10" r="20" fill="#2196f3"/>
    <circle cx="-40" cy="70" r="20" fill="#2196f3"/>
    <circle cx="40" cy="70" r="20" fill="#2196f3"/>
    <text x="0" cy="15" fill="white" text-anchor="middle">5</text>
    <text x="-40" y="75" fill="white" text-anchor="middle">3</text>
    <text x="40" y="75" fill="white" text-anchor="middle">4</text>
  </g>
  
  <!-- 右边的小顶堆 -->
  <g transform="translate(450,100)">
    <text x="0" y="-20" text-anchor="middle" fill="#4caf50">较大的一半(小顶堆)</text>
    <path d="M 0 0 L -60 60 L 60 60 Z" fill="none" stroke="#4caf50" stroke-width="2"/>
    <circle cx="0" cy="10" r="20" fill="#4caf50"/>
    <circle cx="-40" cy="70" r="20" fill="#4caf50"/>
    <circle cx="40" cy="70" r="20" fill="#4caf50"/>
    <text x="0" y="15" fill="white" text-anchor="middle">6</text>
    <text x="-40" y="75" fill="white" text-anchor="middle">8</text>
    <text x="40" y="75" fill="white" text-anchor="middle">7</text>
  </g>
  
  <!-- 中位数指示 -->
  <g transform="translate(300,250)">
    <text x="0" y="0" text-anchor="middle" font-size="16">中位数 = (5 + 6) / 2 = 5.5</text>
    <path d="M -150 -130 L 0 -20 L 150 -130" fill="none" stroke="#ff5722" stroke-width="2" stroke-dasharray="5,5"/>
  </g>
</svg>

🌟 面试时怎么说？

1. 开场白

   • "我们可以用两个堆来维护数据流的中位数"
   • "一个堆存较小的一半，一个堆存较大的一半"

2. 解释优势

   • 时间复杂度：添加数字O(logn)，查找中位数O(1)
   • 空间复杂度：O(n)存储所有数字

3. 补充说明

   • 解决方案的可扩展性
   • 处理大数据流的能力

🎩 扩展思考

这个解决方案的思路还可以用在其他场景：

1. 滑动窗口中位数

   // 在固定大小的窗口中维护中位数
   class SlidingWindowMedian {
       // 类似的双堆结构，加上删除操作
   }

2. 数据流的百分位数

   // 扩展到计算任意百分位的数值
   class PercentileFinder {
       // 可以调整两个堆的比例
   }

这个双堆的设计非常优雅，它告诉我们：有时候把数据分成两半处理，反而能得到更简单的解决方案！

---

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #堆 #数据结构

如果你对这个话题还有任何疑问，欢迎在评论区讨论！理解了这个问题，你会发现很多看似复杂的数据流问题都能用类似的思路来解决。