【问题】如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
【思路】由于是让我们取出一个数据流的中位数，因此我们可以使用最大堆和最小堆，首先我们建立两个堆分别为最大堆和最小堆，首先我们要清楚的是两点问题：
两个堆的大小要么相等（偶数），要么相差为1（奇数），最大堆为较多的
如果想取出中位数，那么较小的数应该在最大堆，较大的数应该在最小堆，从而在奇数情况下，中位数为两个堆堆顶之和/2.0
因此我们每插入一个数据，首先和最大堆堆顶比较，如果大于，则将该数插入最小堆（存放较大的数），否则插入到最大堆，接着需要维护两个堆的大小，maxheap.size = minheap.size或者maxheap.size = minheap.size+1. 如果不满足，则将多的堆的堆顶pop出来放入到少的堆中。
class Solution { public: void Insert(int num) { if(maxheap.empty() || num < maxheap.top()) maxheap.push(num); else minheap.push(num); if(maxheap.size() == minheap.size()+2){ minheap.push(maxheap.top()); maxheap.pop(); } if(maxheap.size() + 1 == minheap.size()){ maxheap.push(minheap.top()); minheap.pop(); } } double GetMedian() { return maxheap.size() == minheap.size() ? (maxheap.top()+minheap.top()) / 2.0 : maxheap.top(); } private: priority_queue<int, vector<int>, less<int>> maxheap; priority_queue<int, vector<int>, greater<int>> minheap; };
原文：https://www.cnblogs.com/zhudingtop/p/11474716.html