题目(数据流中的中位数—牛客网)
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用 Insert() 方法读取数据流，使用 GetMedian() 方法获取当前读取数据的中位数。
算法思路
本题解法有很多，比如如果数组无序，那么使用快速排序中的 Partition 函数可在 O(n) 时间内找到中位数，O(1)时间内插入无序数组;还可以每插入一个元素保持数组有序，那么插入元素需要 O(n) 的时间，而找到中位数只需要 O(1) 的时间(此情况同链表实现)；最后一种，也是下面的实现，即利用最大堆和最小堆，那么怎么操作呢？
首先我们定义一个计数变量 count，然后将第奇数个数插入最大堆，第偶数个数插入最小堆，这是为了保证两个堆的大小之差为 1。注意，插入并不是无条件的，当插入最大堆时，若待插入的元素比最小堆堆顶元素还大，那么先将其插入最小堆后取其新堆顶元素加入最大堆；同理，当插入最小堆时，若待插入的元素比最大堆堆顶元素还小，那么先将其插入最大堆后取其新堆顶元素加入最小堆。这样既保证了将数字平均分配到了两个堆中，也保证了最大堆中的数字都比最小堆中的数字小，以便快速找到中位数。那么此时，很容易得到中位数，如果输入了奇数个数，那么最大堆堆顶元素即中位数，否则中位数为两堆顶元素的平均值。
算法实现
复杂度
本算法实现的时间复杂度为：插入时间为 O(logn)，获取中位数的时间为 O(1)。空间复杂度为两个堆的大小。
参考
[1] <<剑指offer2>>
[2] 牛客网