找出序列中的中位数

一个随机序列，找出序列的中位数，当序列个数为奇数时，为中间位置上的数字；当序列为偶数时，为中间两个数字的平均值。
这种题有很多种做法，比较有代表性的由：
1、partition法
利用快排关键字的查找方法
a.随机选取一个关键字key，将序列二分；
b.若关键字的下标大于N/2，则继续对序列的左半部分执行partition；
c.若关键字的下标小于N/2，则继续对序列的左半部分执行partition；
d.若关键字的下标等于N/2，则返回key。

这种算法：partition的时间复杂度为O(n)，获取中位数的时间复杂度为O(1)。

2、利用平衡二叉查找树
没读取一个数字，将数字插入到二叉树中，并调整二叉树的平衡性。最后根节点就是想要的中位数。

构建平衡二叉查找树的算法时间复杂度为O(logn)，取出中位数的时间复杂度为O（n）。但是调整平衡二叉查找树算法实现比较复杂。

3.利用堆
原理分析：中位数无非就是将序列分为两个部分，左边的部分都小于中位数，右边的序列都大于中位数。这比较符合堆的特性（看看数据结构在算法中的重要性，选择好的数据结构能够让算法事半功倍）。可以将序列分成两个部分，左边的部分够着大根堆，右边的部分构造小根堆。

具体实现细节：
a.如果堆中元素的个数为偶数时，将新数字插入小根堆中（插入后堆元素的个数为奇数，此时结束插入，返回小根堆堆顶元素）；如果堆中的元素个数为奇数时，将新数字插入大根堆中（插入后堆元素的个数为偶数，此时结束插入，返回两堆堆顶元素的均值）。
b.若插入小根堆的元素大于大根堆堆顶的元素，说明新元素位于序列的右半部分，应当插入大根堆。而此时大根堆堆顶元素应当位于左半序列（小顶堆）中，因此需要将大根堆堆顶元素插入小根堆。若插入若插入小顶堆的元素不大于大顶堆堆顶的元素，则直接插入小根堆。
c.同理，向大根堆插入元素时也有如上考虑。

调整堆的时间复杂度为O（logn），取中位数的时间复杂度为O(1)。
算法实现：

template <typename T>
class Solution {
public:
    vector<T> minHeap;
    vector<T> maxHeap;
    void Insert(T num)
    {
        //判断数据插入的堆
        //奇数时插入大顶堆，偶数时插入小顶堆
        if((minHeap.size()+maxHeap.size())&0x01){
            if(minHeap.size() > 0 && minHeap[0] < num){
                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{
            if(maxHeap.size() > 0&& maxHeap[0] > num){
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(),maxHeap.end(),less<int>());

                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>());
        }
    }

    T GetMedian()
    { 
        int size = minHeap.size() + maxHeap.size();
        if(size <= 0) return -1;
        double result=0.0;
        if(size & 0x01) result = minHeap[0];
        else result = (minHeap[0]+maxHeap[0])/2;

        return result;

    }

};