题目
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
样例
输入：1, 2, 3, 4
输出：1,1.5,2,2.5
解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

解法：堆

得到中位数需要对数组进行动态排序，常规的快排等方法复杂度无法接受，因为它们每次都对所有数字进行排序，我们希望只需要对局部进行排序，更准确地说，得到中间两个数
可以考虑使用两个堆，将所有数分成较小的和较大的两个部分，较小的放入大根堆，得到其中最大的，较大的放入小根堆，得到其中最小的，那么两个堆的堆顶就是中位数的候选者
时间复杂度O(nlogn)，空间复杂度O(n)

  1. class Solution {
  2. public:
  3.     priority_queue<int> max_heap;
  4.     priority_queue<int, vector<int>, greater<int>> min_heap;
  6.     void insert(int num){
  7.         max_heap.push(num);
  8.         if (min_heap.size() && max_heap.top() > min_heap.top()) {
  9.             auto max_v = max_heap.top(), min_v = min_heap.top();
  10.             max_heap.pop(), min_heap.pop();
  11.             max_heap.push(min_v), min_heap.push(max_v);
  12.         }
  13.         if (max_heap.size() > min_heap.size() + 1) {
  14.             min_heap.push(max_heap.top());
  15.             max_heap.pop();
  16.         }
  17.     }
  19.     double getMedian(){
  20.         if (max_heap.size() > min_heap.size()) return max_heap.top();
  21.         return (max_heap.top() + min_heap.top()) / 2.0;
  22.     }
  23. };