```
from heapq import *
class MaxHeap(object):
def __init__(self):
self.heap = []
def __len__(self):
return len(self.heap)
def push(self, num):
heappush(self.heap, -num)
def pop(self):
return -heappop(self.heap)
def pushpop(self, num):
return -heappushpop(self.heap, -num)
def getMax(self):
return -self.heap[0]
class MinHeap(object):
def __init__(self):
self.heap = []
def __len__(self):
return len(self.heap)
def push(self, num):
heappush(self.heap, num)
def pop(self):
return heappop(self.heap)
def pushpop(self, num):
return heappushpop(self.heap, num)
def getMin(self):
return self.heap[0]
class MedianFinder(object):
def __init__(self):
"""
initialize your data structure here.
"""
# Constaints:
# - Minheap must only store elements > median.
# - Maxheap must only store elements < median.
# - len(maxheap) >= len(minheap), but lengths must differ by at most one.
self.minheap = MinHeap()
self.maxheap = MaxHeap()
def addNum(self, num):
"""
:type num: int
:rtype: void
"""
# Must maintain the constraint that len(maxheap) >= len(minheap) by at most one element throughout.
if len(self.maxheap) == len(self.minheap):
# Add num to maxheap, then re-balance both heaps to maintain all constraints.
self.minheap.push(self.maxheap.pushpop(num))
self.maxheap.push(self.minheap.pop())
else:
# Must be the case that len(maxheap) = len(minheap) + 1, so add num to minheap, and re-balance heaps to maintain all constraints.
self.maxheap.push(self.minheap.pushpop(num))
self.minheap.push(self.maxheap.pop())
def findMedian(self):
"""
:rtype: float
"""
if len(self.minheap) == len(self.maxheap):
return float(self.maxheap.getMax() + self.minheap.getMin()) / 2
else:
return float(self.maxheap.getMax())
```