剑指offer-面试题41-数据流中的中位数-堆

/*
题目：
	链接：https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
	来源：牛客网
	如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
	如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
	我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
*/
/*
思路：
	将数据流分成两堆，左边一堆的值小于右边一堆的值。
	当为奇数个时，中位数为左堆里的最大值；当为偶数个时，中位数为（左堆最大值+右堆最小值）/2.
	左堆为最大堆，右堆为最下堆。
*/
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<set>
#include<vector>

using namespace std;


multiset<int,greater<int>> leftSet;
multiset<int,less<int>> rightSet;
multiset<int,greater<int>>::iterator leftIter;
multiset<int,less<int>>::iterator rightIter;
int myCount = 0;
void Insert(int num)
{

    if(myCount % 2 == 0){//当前个数为偶数，将num插到左堆
        if(rightSet.empty() || *(rightSet.begin()) >= num){//当右堆为空或右堆最小值大于等于num，直接插入左堆
            leftSet.insert(num);
        }
        else{//当右堆最大值小于num，将右堆最小值放到左堆，将num放到右堆。
            rightIter = rightSet.begin();
            leftSet.insert(*rightIter);
            rightSet.erase(rightIter);
            rightSet.insert(num);
        }
    }else{//当前个数为奇数，将num插到右堆
        if(*(leftSet.begin()) <= num){//当左堆最大值小于等于num，直接插入右堆
            rightSet.insert(num);
        }else{//当左堆最大值大于num，将左堆最大值放到右堆，将num放到左堆。
            leftIter = leftSet.begin();
            rightSet.insert(*leftIter);
            leftSet.erase(leftIter);
            leftSet.insert(num);
        }
    }
    myCount++;
}

double GetMedian()
{
    if(myCount % 2 == 1){
        return *(leftSet.begin());
    }else{
        return ((double)(*(leftSet.begin())) + (double)(*(rightSet.begin())))/2;
    }

}

int main(){

    Insert(5);

    Insert(2);
    Insert(3);
    Insert(4);
    Insert(1);
    Insert(6);
    Insert(7);
    Insert(0);
    Insert(8);

    cout<<GetMedian()<<endl;


}