I keep two heaps (or priority queues):

- Max-heap
`small`

has the smaller half of the numbers. - Min-heap
`large`

has the larger half of the numbers.

This gives me direct access to the one or two middle values (they're the tops of the heaps), so getting the median takes O(1) time. And adding a number takes O(log n) time.

Supporting both min- and max-heap is more or less cumbersome, depending on the language, so I simply negate the numbers in the heap in which I want the reverse of the default order. To prevent this from causing a bug with -2^{31} (which negated is itself, when using 32-bit ints), I use integer types larger than 32 bits.

Using larger integer types also prevents an overflow error when taking the mean of the two middle numbers. I think almost all solutions posted previously have that bug.

**Update:** These are pretty short already, but by now I wrote even shorter ones.

**Java**

```
class MedianFinder {
private Queue<Long> small = new PriorityQueue(),
large = new PriorityQueue();
public void addNum(int num) {
large.add((long) num);
small.add(-large.poll());
if (large.size() < small.size())
large.add(-small.poll());
}
public double findMedian() {
return large.size() > small.size()
? large.peek()
: (large.peek() - small.peek()) / 2.0;
}
};
```

Props to larrywang2014's solution for making me aware that I can use Queue in the declaration instead of PriorityQueue (that's all I got from him, though (just saying because I just saw he changed his previously longer addNum and it's now equivalent to mine)).

**C++**

```
class MedianFinder {
priority_queue<long> small, large;
public:
void addNum(int num) {
small.push(num);
large.push(-small.top());
small.pop();
if (small.size() < large.size()) {
small.push(-large.top());
large.pop();
}
}
double findMedian() {
return small.size() > large.size()
? small.top()
: (small.top() - large.top()) / 2.0;
}
};
```

Big thanks to jianchao.li.fighter for telling me that C++'s priority_queue is a max-queue (see comments below).

**Python**

```
from heapq import *
class MedianFinder:
def __init__(self):
self.heaps = [], []
def addNum(self, num):
small, large = self.heaps
heappush(small, -heappushpop(large, num))
if len(large) < len(small):
heappush(large, -heappop(small))
def findMedian(self):
small, large = self.heaps
if len(large) > len(small):
return float(large[0])
return (large[0] - small[0]) / 2.0
```