Very Short, O(log n) + O(1)
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 me
Same idea [as before](https://leetcode.com/discuss/64850/short-simple-java-c-python-o-log-n-o-1), 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](https://leetcode.com/discuss/64852/ac-python-two-heap-solution-o-log-n-add-o-1-find-388-ms).\n\n**Update:** Added a new Java version (the first one).\n\n---\n\n**Java**\n\n    class MedianFinder {\n        \n        Queue<Integer> q = new PriorityQueue(), z = q, t,\n                       Q = new PriorityQueue(Collections.reverseOrder()); \n    \n        public void addNum(int num) {\n            (t=Q).add(num);\n            (Q=q).add((q=t).poll());\n        }\n    \n        public double findMedian() {\n            return (Q.peek() + z.peek()) / 2.;\n        }\n    };\n\nOr:\n\n    class MedianFinder {\n    \n        Queue[] q = {new PriorityQueue(), new PriorityQueue(Collections.reverseOrder())};\n        int i = 0;\n    \n        public void addNum(int num) {\n            q[i].add(num);\n            q[i^=1].add(q[i^1].poll());\n        }\n    \n        public double findMedian() {\n            return ((int)(q[1].peek()) + (int)(q[i].peek())) / 2.0;\n        }\n    };\n\n---\n\n**Python**\n\n    from heapq import *\n\n    class MedianFinder:\n    \n        def __init__(self):\n            self.heaps = None, [], []\n            self.i = 1\n    \n        def addNum(self, num):\n            heappush(self.heaps[-self.i], -heappushpop(self.heaps[self.i], num * self.i))\n            self.i *= -1\n    \n        def findMedian(self):\n            return (self.heaps[self.i][0] * self.i - self.heaps[-1][0]) / 2.0\n\nOr:\n\n    from heapq import *\n\n    class MedianFinder:\n    \n        def __init__(self):\n            self.data = 1, [], []\n    \n        def addNum(self, num):\n            sign, h1, h2 = self.data\n            heappush(h2, -heappushpop(h1, num * sign))\n            self.data = -sign, h2, h1\n    \n        def findMedian(self):\n            sign, h1, h2 = d = self.data\n            return (h1[0] * sign - d[-sign][0]) / 2.0\n\nOr:\n```\nclass MedianFinder:\n    def __init__(s):\n        h = [[], 1, -1, i := []]\n        s.addNum = lambda n: heapq.heappush(h[-1], -heapq.heappushpop(h[0], n * h[1])) or h.reverse()\n        s.findMedian = lambda: (h[0][0] * h[1] - i[0]) / 2\n
['Heap (Priority Queue)', 'Python', 'Java']