Short simple Java/C++/Python, O(log n) + O(1)
I keep two heaps (or priority queues):\n\n- Max-heap small has the smaller half of the numbers.\n- Min-heap large has the larger half of the numbers.\n\nThis gi
I keep two heaps (or priority queues):\n\n- Max-heap `small` has the smaller half of the numbers.\n- Min-heap `large` has the larger half of the numbers.\n\nThis gives me direct access to the one or two middle values (they're the tops of the heaps), so getting the median takes O(1) time. And adding a number takes O(log n) time.\n\nSupporting both min- and max-heap is more or less cumbersome, depending on the language, so I simply negate the numbers in the heap in which I want the reverse of the default order. To prevent this from causing a bug with -2<sup>31</sup> (which negated is itself, when using 32-bit ints), I use integer types larger than 32 bits.\n\nUsing larger integer types also prevents an overflow error when taking the mean of the two middle numbers. I think almost all solutions posted previously have that bug.\n\n**Update:** These are pretty short already, but by now I wrote [even shorter ones](https://leetcode.com/discuss/64910/very-short-o-log-n-o-1).\n\n---\n\n**Java**\n\n    class MedianFinder {\n    \n        private Queue<Long> small = new PriorityQueue(),\n                            large = new PriorityQueue();\n    \n        public void addNum(int num) {\n            large.add((long) num);\n            small.add(-large.poll());\n            if (large.size() < small.size())\n                large.add(-small.poll());\n        }\n    \n        public double findMedian() {\n            return large.size() > small.size()\n                   ? large.peek()\n                   : (large.peek() - small.peek()) / 2.0;\n        }\n    };\n\nProps to [larrywang2014's solution](https://leetcode.com/discuss/64842/32ms-easy-to-understand-java-solution) for making me aware that I can use Queue in the declaration instead of PriorityQueue (that's all I got from him, though (just saying because I just saw he changed his previously longer addNum and it's now equivalent to mine)).\n\n---\n\n**C++**\n\n    class MedianFinder {\n        priority_queue<long> small, large;\n    public:\n    \n        void addNum(int num) {\n            small.push(num);\n            large.push(-small.top());\n            small.pop();\n            if (small.size() < large.size()) {\n                small.push(-large.top());\n                large.pop();\n            }\n        }\n    \n        double findMedian() {\n            return small.size() > large.size()\n                   ? small.top()\n                   : (small.top() - large.top()) / 2.0;\n        }\n    };\n\nBig thanks to jianchao.li.fighter for telling me that C++'s priority_queue is a max-queue (see comments below).\n\n---\n\n**Python**\n\n    from heapq import *\n    \n    class MedianFinder:\n    \n        def __init__(self):\n            self.heaps = [], []\n    \n        def addNum(self, num):\n            small, large = self.heaps\n            heappush(small, -heappushpop(large, num))\n            if len(large) < len(small):\n                heappush(large, -heappop(small))\n    \n        def findMedian(self):\n            small, large = self.heaps\n            if len(large) > len(small):\n                return float(large[0])\n            return (large[0] - small[0]) / 2.0
['Heap (Priority Queue)']