如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

利用大顶堆小顶堆的思想（具体参考书）

class Solution {
public:
    vector<int> maxHeap;//最大堆，存储的是左边部分值，总体小于右边部分，最大值位于堆顶
    vector<int> minHeap;//最小堆，存储的是右边部分值，总体大于右边部分，最小值位于堆顶

    void Insert(int num)
    {
        if (((minHeap.size() + maxHeap.size()) & 0x1) == 0)
        {
        /*
        当数据总数为偶数时，计划将要插入的数放入最小堆中。（奇数则分配到大顶堆，这样保持两边分配均匀，任何时候相差不超过1.
        为了保证最小堆整体大于最大堆。
        if num<大顶堆的最大值(maxHeap[0])
            则将num插入大顶堆，此时大顶堆多了一个元素；
            则把大顶堆的最大值删掉，插入最小堆中。
        else:
            插入到最小堆中。
        */
            if (maxHeap.size() > 0 && num < maxHeap[0])
            {
                //添加num到大顶堆
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(),less<int>());//仿函数less保证插入后仍为大顶堆
                //将大顶堆的堆顶元素删除并插入到小顶堆中
                num = maxHeap[0];
                pop_heap(maxHeap.begin(), maxHeap.end(),less<int>());
                maxHeap.pop_back();

                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(),greater<int>());//仿函数greater保证插入后仍为小顶堆
            }
            else
            {
                //正常插入到小顶堆
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(),greater<int>());
            }
        }

        else
        {
            /*
            当数据总数为奇数时，计划将要插入的数放入最大堆中。
            为了保证最小堆整体大于最大堆。
            if num>小顶堆的最小值(minHeap[0])
                则将num插入小顶堆，此时小顶堆多了一个元素；
                则把小顶堆的最小值删掉，插入最大堆中。
            else:
                插入到最大堆中。
            */
            if (minHeap.size() > 0 && num > minHeap[0])
            {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(),greater<int>());

                num = minHeap[0];
                pop_heap(minHeap.begin(), minHeap.end(),greater<int>());
                minHeap.pop_back();

                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<int>());
            }
            else
            {
                //正常插入到大顶堆
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<int>());
            }
        }
    }

    double GetMedian()
    {
        double midNum=0;
        int totalSi***Heap.size() + maxHeap.size();
        if (totalSize == 0)
            return 0;
        //若总数为偶数时，中位数为大顶堆堆顶+小顶堆堆顶的一半；
        //若总数为奇数时，中位数为小顶堆的堆顶值。(因为在插入的时候总数为偶数插入小顶堆，所以小顶堆为较多的一方)
        if ((totalSize & 0x1) == 0)
            midNum = (minHeap[0] + maxHeap[0]) / 2.0;
        else
            midNum = minHeap[0];
        return midNum;
    }
};

这里注意几点的是：

1. 在利用push_heap或pop_heap添加或删除堆元素之前，要保证已经是一个堆了。
2. 大顶堆以及升序的例子，sort_heap或sort第三个参数为less<int>();
   小顶堆以及降序的例子，sort_heap或sort第三个参数为greater<int>();头文件为#include<functional>