Java | Two Heaps algo | Explained through comments
\nclass MedianFinder {\n    \n    // To store lower half of data stream eg. 1, 2, 3, 6\n    PriorityQueue<Integer> lowerHalf;\n    // To store upper half of dat
```\nclass MedianFinder {\n    \n    // To store lower half of data stream eg. 1, 2, 3, 6\n    PriorityQueue<Integer> lowerHalf;\n    // To store upper half of data stream eg. 8, 9, 11\n    PriorityQueue<Integer> upperHalf;\n\n    /** initialize your data structure here. */\n    public MedianFinder() {\n        lowerHalf = new PriorityQueue<>((a,b) -> b - a); // Max heap : To fetch largest\n        // element from lower half in O(1) time\n        upperHalf = new PriorityQueue<>(); // Min heap : To fetch lowest \n        // element from upper half in O(1) time\n    }\n    \n    public void addNum(int num) {\n        // Insert in lowerHalf is it\'s empty or if number being inserted is less than the peek of lowerHalf otherwise insert in upperHalf\n        if(lowerHalf.isEmpty() || num <= lowerHalf.peek()){\n            lowerHalf.add(num);\n        }else{\n            upperHalf.add(num);\n        }\n        \n        // We also need to ensure that the halves are balanced i.e. there is no more than a difference of 1 in size of both halves\n        // Let lowerHalf be the one to hold one extra element if the size of total data stream is odd otherwise be equal to upperHalf\n        if(upperHalf.size() > lowerHalf.size()){ // If an element added above made upperHalf have one more element than lowerHalf then we poll it and put it into lowerHalf\n            lowerHalf.add(upperHalf.poll());\n        } else if(lowerHalf.size() > upperHalf.size() + 1){\n            // If an element added above, made lowerHalf have 2 more elements then upperHalf then we put one into upperHalf from lowerHalf\n            upperHalf.add(lowerHalf.poll());\n        }\n    }\n    \n    public double findMedian() {\n        if(lowerHalf.size() == upperHalf.size()){\n            return (double)(lowerHalf.peek() + upperHalf.peek())/2;\n        }else{\n             return (double)(lowerHalf.peek());\n        }\n    }\n}\n\n/**\n * Your MedianFinder object will be instantiated and called as such:\n * MedianFinder obj = new MedianFinder();\n * obj.addNum(num);\n * double param_2 = obj.findMedian();\n */\n```
['Heap (Priority Queue)', 'Java']