剑指offer——数据流中的中位数计算

题目描述

在数据流中如何确定中位数？当从数据流中读取奇数个数值时，中位数即为所有数值排序后处于正中间的那个数值。而当读取偶数个数值时，中位数则为排序后位于中间位置的两个数值的平均值。

分析

获取数据流中的中位数存在多种实现方式，但不同方式在时间效率方面存在差异。以下是对几种方法的时间复杂度进行比较的结果：通过图表可知，采用AVL二叉平衡树和最大堆与最小堆结合的方式，在总体时间复杂度上表现最为优越。然而，AVL二叉平衡树缺乏现成的数据结构支持，因此可考虑借助Java集合框架中的PriorityQueue优先队列（即堆结构，默认为小根堆）来实现较为高效的中位数查找过程。

思路：将数据序列从中间位置进行划分，左侧部分采用大根堆进行存储，右侧部分则通过小根堆实现。在逐个处理数据的过程中，计数器count随之递增。若当前count为偶数，则将该数据插入至小根堆中；若当前count为奇数，则将其插入到大根堆中。当所有数据完成插入操作后（该过程的时间复杂度为O(logn)），若最终count为偶数，则中位数等于大根堆顶部元素与小根堆顶部元素之