Java数据流中位数计算：现有实现方案是否可行？

嘿，这个需求完全是可以实现的，而且有非常成熟的高效方案哦！不用太担心，咱们一步步来梳理。

这是业界处理动态数据流中位数的标准思路，比每次插入后全量排序要高效得多，而且能完美支持任意数量的输入。核心是维护两个堆：

• 大顶堆：专门存数据流里较小的那一半元素，堆顶是这部分的最大值
• 小顶堆：专门存数据流里较大的那一半元素，堆顶是这部分的最小值

关键维护规则 #

为了能快速算出中位数，咱们得保证两个堆的状态始终符合以下要求：

• 两个堆的大小差不能超过1：要么大小完全相等，要么大顶堆比小顶堆多1个元素
• 大顶堆里的所有元素，必须小于等于小顶堆里的所有元素

插入新元素的步骤 #

1. 先把新元素扔进大顶堆
2. 把大顶堆的堆顶元素（也就是当前小半部分的最大值）移到小顶堆——这一步是为了保证两个堆的元素大小边界正确
3. 如果小顶堆的大小超过了大顶堆，就把小顶堆的堆顶（当前大半部分的最小值）移回大顶堆，维持大小平衡

计算中位数的逻辑 #

• 如果两个堆大小相等：中位数就是两个堆顶元素的平均值
• 如果大顶堆比小顶堆多1个元素：中位数就是大顶堆的堆顶元素

Java 代码示例（可直接运行） #

Java 自带的PriorityQueue默认是小顶堆，所以大顶堆需要自定义比较器来实现：

import java.util.PriorityQueue;
import java.util.Scanner;

public class MedianCalculator {
    // 大顶堆：存储较小的一半元素
    private PriorityQueue<Integer> maxHeap;
    // 小顶堆：存储较大的一半元素
    private PriorityQueue<Integer> minHeap;

    public MedianCalculator() {
        // 用Lambda表达式实现大顶堆的比较逻辑
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>(); // 默认是小顶堆
    }

    public void addNumber(int num) {
        // 第一步：先加入大顶堆
        maxHeap.offer(num);
        // 第二步：平衡元素大小边界
        minHeap.offer(maxHeap.poll());
        // 第三步：平衡两个堆的大小
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double getMedian() {
        if (maxHeap.size() == minHeap.size()) {
            // 偶数个元素，取两个堆顶的平均值
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            // 奇数个元素，大顶堆顶就是中位数
            return maxHeap.peek();
        }
    }

    public static void main(String[] args) {
        MedianCalculator calculator = new MedianCalculator();
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入数字（输入非数字即可结束程序）：");
        
        while (scanner.hasNextInt()) {
            int input = scanner.nextInt();
            calculator.addNumber(input);
            System.out.println("更新后的中位数：" + calculator.getMedian());
        }
        
        scanner.close();
        System.out.println("程序结束～");
    }
}

关于你现有代码的可能问题 #

如果你的代码是每次插入后都对整个数组进行排序（比如用Arrays.sort()），理论上小数据量时能工作，但数据量变大后效率会急剧下降（每次排序是O(nlogn)复杂度），而且如果你的数组扩容、索引计算或者排序后的中位数取数逻辑有边界错误，就可能在超过4个元素时出现异常。

而双堆法每次插入的复杂度是O(logn)，不管输入多少元素都能稳定运行，非常适合数据流这种动态添加的场景。

内容的提问来源于stack exchange，提问作者Java_Beginner