Same idea as before, but really exploiting the symmetry of the two heaps by switching them whenever a number is added. Still O(log n) for adding and O(1) for median. Partially inspired by peisi's updated solution.

**Update:** Added a new Java version (the first one).

**Java**

```
class MedianFinder {
Queue<Integer> q = new PriorityQueue(), z = q, t,
Q = new PriorityQueue(Collections.reverseOrder());
public void addNum(int num) {
(t=Q).add(num);
(Q=q).add((q=t).poll());
}
public double findMedian() {
return (Q.peek() + z.peek()) / 2.;
}
};
```

Or:

```
class MedianFinder {
Queue[] q = {new PriorityQueue(), new PriorityQueue(Collections.reverseOrder())};
int i = 0;
public void addNum(int num) {
q[i].add(num);
q[i^=1].add(q[i^1].poll());
}
public double findMedian() {
return ((int)(q[1].peek()) + (int)(q[i].peek())) / 2.0;
}
};
```

**Python**

```
from heapq import *
class MedianFinder:
def __init__(self):
self.heaps = None, [], []
self.i = 1
def addNum(self, num):
heappush(self.heaps[-self.i], -heappushpop(self.heaps[self.i], num * self.i))
self.i *= -1
def findMedian(self):
return (self.heaps[self.i][0] * self.i - self.heaps[-1][0]) / 2.0
```

Or:

```
from heapq import *
class MedianFinder:
def __init__(self):
self.data = 1, [], []
def addNum(self, num):
sign, h1, h2 = self.data
heappush(h2, -heappushpop(h1, num * sign))
self.data = -sign, h2, h1
def findMedian(self):
sign, h1, h2 = d = self.data
return (h1[0] * sign - d[-sign][0]) / 2.0
```