Python O(lgn) using two heapq data sturctures
class MedianFinder:\n    import heapq\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.small = [] 
    class MedianFinder:\n    import heapq\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.small = [] # store the small half, top is the largest in the small part\n        self.large = [] # store the large half, top is the smallest in the large part\n\n    def addNum(self, num):\n        """\n        Adds a num into the data structure.\n        :type num: int\n        :rtype: void\n        """\n        if len(self.small) == 0:\n            heapq.heappush(self.small, -num)\n            return\n        if num <= -self.small[0]:\n            # push to small part\n            heapq.heappush(self.small, -num)\n        else:\n            # push to large part\n            heapq.heappush(self.large, num)\n        # adjust small and large balance\n        if len(self.small) - len(self.large) == 2:\n            heapq.heappush(self.large, -heapq.heappop(self.small))\n        elif len(self.small) - len(self.large) == -2:\n            heapq.heappush(self.small, -heapq.heappop(self.large))\n\n    def findMedian(self):\n        """\n        Returns the median of current data stream\n        :rtype: float\n        """\n        if len(self.small) == len(self.large):\n            return (self.large[0] - self.small[0])/2.0\n        return -float(self.small[0]) if len(self.small) > len(self.large) else float(self.large[0])
[]