Java/Python two heap solution, O(log n) add, O(1) find
The invariant of the algorithm is two heaps, small and large, each represent half of the current list. The length of smaller half is kept to be n / 2 at all tim
The invariant of the algorithm is two heaps, small and large, each represent half of the current list. The length of smaller half is kept to be n / 2 at all time and the length of the larger half is either n / 2 or n / 2 + 1 depend on n's parity. \n\nThis way we only need to peek the two heaps' top number to calculate median.\n\nAny time before we add a new number, there are two scenarios, (total n numbers, k = n / 2):\n\n    (1) length of (small, large) == (k, k)\n    (2) length of (small, large) == (k, k + 1)\n\nAfter adding the number, total (n + 1) numbers, they will become:\n\n    (1) length of (small, large) == (k, k + 1)\n    (2) length of (small, large) == (k + 1, k + 1)\n\nHere we take the first scenario for example, we know the large will gain one more item and small will remain the same size, but we cannot just push the item into large. What we should do is we push the new number into small and pop the maximum item from small then push it into large (all the pop and push here are heappop and heappush). By doing this kind of operations for the two scenarios we can keep our invariant.\n\nTherefore to add a number, we have 3 O(log n) heap operations. Luckily the heapq provided us a function "heappushpop" which saves some time by combine two into one. The document says:\n\n<blockquote>Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().</blockquote>\n\nAlltogether, the add operation is O(logn), The findMedian operation is O(1). \n\nNote that the heapq in python is a min heap, thus we need to invert the values in the smaller half to mimic a "max heap".\n\nA further observation is that the two scenarios take turns when adding numbers, thus it is possible to combine the two into one. For this please see [stefan's post][1]\n\n\n**Java**\n\n    private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());\n    private PriorityQueue<Integer> large = new PriorityQueue<>();\n    private boolean even = true;\n\n    public double findMedian() {\n        if (even)\n            return (small.peek() + large.peek()) / 2.0;\n        else\n            return small.peek();\n    }\n\n    public void addNum(int num) {\n        if (even) {\n            large.offer(num);\n            small.offer(large.poll());\n        } else {\n            small.offer(num);\n            large.offer(small.poll());\n        }\n        even = !even;\n    }\n\n\n**Python**\n\n    from heapq import *\n    \n    \n    class MedianFinder:\n        def __init__(self):\n            self.small = []  # the smaller half of the list, max heap (invert min-heap)\n            self.large = []  # the larger half of the list, min heap\n    \n        def addNum(self, num):\n            if len(self.small) == len(self.large):\n                heappush(self.large, -heappushpop(self.small, -num))\n            else:\n                heappush(self.small, -heappushpop(self.large, num))\n    \n        def findMedian(self):\n            if len(self.small) == len(self.large):\n                return float(self.large[0] - self.small[0]) / 2.0\n            else:\n                return float(self.large[0])\n\n    # 18 / 18 test cases passed.\n    # Status: Accepted\n    # Runtime: 388 ms\n\n\n\n\n  [1]: https://leetcode.com/discuss/64910/very-short-o-log-n-o-1
['Heap (Priority Queue)', 'Python', 'Java']