・Two `multiset`

are used to sort the numbers.

・Data stream numbers are divided into these two `multiset`

. `multiset 1`

's numbers are greater than `multiset 2`

's.

・Keep size of `multiset 1`

is equal to size of `multiset 2`

or equal to size of `multiset 2`

+1.

```
class MedianFinder
{
private:
multiset<int> s1, s2;
public:
// Adds a number into the data structure.
void addNum(int n)
{
int t;
multiset<int>::iterator it;
if (s1.empty() || n <= *s1.rbegin())
s1.insert(n);
else
s2.insert(n);
if (s1.size() > s2.size() + 1)
{
it = s1.end();
t = *(--it);
s1.erase(it); //t=*it need to be done before erase(it);
s2.insert(t);
}
else if (s2.size() > s1.size())
{
t = *s2.begin();
s2.erase(s2.begin());
s1.insert(t);
}
return;
}
// Returns the median of current data stream
double findMedian()
{
if (s1.size() > s2.size())
return (double)*s1.rbegin();
double d1, d2;
d1 = (double)*s1.rbegin();
d2 = (double)*s2.begin();
return (d1 + d2) / 2.0;
}
};
```

After I watched discussions, there is a container whose name is priority_queue and can use negated numbers.