Easy to understand double-heap solution in Java
The basic idea is to maintain two heaps: a max-heap and a min-heap. The max heap stores the smaller half of all numbers while the min heap stores the larger hal
The basic idea is to maintain two heaps: a max-heap and a min-heap. **The max heap stores the smaller half of all numbers while the min heap stores the larger half.** The sizes of two heaps need to be balanced each time when a new number is inserted so that their size will not be different by more than 1. Therefore each time when findMedian() is called we check if two heaps have the same size. If they do, we should return the average of the two top values of heaps. Otherwise we return the top of the heap which has one more element.\n\nTo do that, we first need to add two PriorityQueues to the class as the max-heap and min-heap:\n\n        private PriorityQueue<Integer> minH;\n        private PriorityQueue<Integer> maxH;\n\nWe then define the constructor of the class so that the PriorityQueues get initialized. By default, the sorting order of a PriorityQueue is natural order which means it is a min-heap by default. Hence we need to provide a new Comparator to the constructor of the max heap to specify the reversed order.\n\n        MedianFinder(){\n            minH = new PriorityQueue<Integer>();\n            maxH = new PriorityQueue<Integer>(1, new Comparator<Integer>(){\n                public int compare(Integer o1, Integer o2) {\n                    if (o1.intValue()>o2.intValue()) return -1;\n                    if (o1.intValue()<o2.intValue()) return 1;\n                    return 0;\n                }\n            });\n        }\n\nNow we have the data structure properly built. Let's write the addNum() function next.\n\n        public void addNum(int num) {\n            if ((minH.size()==0)&&(maxH.size()==0)) minH.add(num);\n            else if ((minH.size())>(maxH.size())) {\n                if (num>minH.peek()) {\n                    maxH.add(minH.poll());\n                    minH.add(num);\n                } else maxH.add(num);\n            } else if ((minH.size())<(maxH.size())) {\n                if (num<maxH.peek()) {\n                    minH.add(maxH.poll());\n                    maxH.add(num);\n                } else minH.add(num);            \n            } else {\n                if (num<maxH.peek()) maxH.add(num);\n                else minH.add(num);             \n            }\n        }\n\nThere are several possible situations when a new number is inserted: \n\n1)If both heap are empty, meaning that we are inserting the first number, we just arbitrarily inserted it into a heap, let's say, the min-heap. \n\n2)If min-heap has more elements (later we will argue that the size won't be different by more than 1), we need to compare the new number with the top of the min-heap. If it is larger than that, then the new number belongs to the larger half and it should be added to the min-heap. But since we have to balance the heap, we should move the top element of the min-heap to the max-heap. For the min-heap, we inserted a new number but removed the original top, its size won't change. For the max-heap, we inserted a new element (the top of the min-heap) so its size will increase by 1.\n\n3)If max-heap has more elements, we did the similar thing as 2).\n\n4)If they have the same size, we just compare the new number with one of the top to determine which heap the new number should be inserted. We just simply inserted it there.\n\nIt can be seen that for each insertion if it was in situation 1) and 4), then after insertion the heap size difference will be 1. For 2) and 3), the size of the heap with fewer element will increase by 1 to catch up with the heap with more elements. Hence their sizes are well-balanced and the difference will never exceeds 1.\n\nObviously, the median will be the top element of the heap which has one more element (if max-heap and min-heap have different sizes), or the average of the two tops (if max-heap and min-heap have equal sizes). So the findMedian() function is very straightforward:\n\n        // Returns the median of current data stream\n        public double findMedian() {\n            if ((minH.size()==0)&&(maxH.size()==0)) return 0.0;\n            if ((minH.size())>(maxH.size())) return (double)(minH.peek());\n            if ((minH.size())<(maxH.size())) return (double)(maxH.peek());\n            return ((double)(maxH.peek()+minH.peek()))/2.0;\n        }\n\n\n\nThe entire codes are here:\n\n    class MedianFinder {\n        private PriorityQueue<Integer> minH;\n        private PriorityQueue<Integer> maxH;\n        \n        MedianFinder(){\n            minH = new PriorityQueue<Integer>();\n            maxH = new PriorityQueue<Integer>(1, new Comparator<Integer>(){\n                public int compare(Integer o1, Integer o2) {\n                    if (o1.intValue()>o2.intValue()) return -1;\n                    if (o1.intValue()<o2.intValue()) return 1;\n                    return 0;\n                }\n            });\n        }\n        \n        \n        // Adds a number into the data structure.\n        public void addNum(int num) {\n            if ((minH.size()==0)&&(maxH.size()==0)) minH.add(num);\n            else if ((minH.size())>(maxH.size())) {\n                if (num>minH.peek()) {\n                    maxH.add(minH.poll());\n                    minH.add(num);\n                } else maxH.add(num);\n            } else if ((minH.size())<(maxH.size())) {\n                if (num<maxH.peek()) {\n                    minH.add(maxH.poll());\n                    maxH.add(num);\n                } else minH.add(num);            \n            } else {\n                if (num<maxH.peek()) maxH.add(num);\n                else minH.add(num);             \n            }\n        }\n    \n        // Returns the median of current data stream\n        public double findMedian() {\n            if ((minH.size()==0)&&(maxH.size()==0)) return 0.0;\n            if ((minH.size())>(maxH.size())) return (double)(minH.peek());\n            if ((minH.size())<(maxH.size())) return (double)(maxH.peek());\n            return ((double)(maxH.peek()+minH.peek()))/2.0;\n        }\n    };\n    \n    // Your MedianFinder object will be instantiated and called as such:\n    // MedianFinder mf = new MedianFinder();\n    // mf.addNum(1);\n    // mf.findMedian();
[]