C++|| Easy to understand || fully commented || Explanation too
Here our main objective is we want the middle element/s(we are not interested in other elements as soon as we get middle one/s) . So we can do it in array but e
Here our main objective is we want the middle element/s(we are not interested in other elements as soon as we get middle one/s) . So we can do it in array but every time we encounter new element we have to fix its position in sorted order which will take O(N) time which seems normal but for a stream of data it is a hell lot of processing. \nNow thinking of this case we can think of priority queues because it guarantees getMin and getMax in O(1) time if some how we just make middle on top(min/max) we can solve this problem.\nSo here we can put constratint that the min heap\'s smallest element should be gerater than or equal to max element of max heap , we are putting this becoz later on if we want the top elements of any heap we can get the middle ones only.\nTo maintain this we will also ensure that the heaps are balanced in terms of size(no. of elements) (i.e., their size should not differ by more than 1 unit).\n***To sum up we can achieve this by following below steps:\n1) Use min heap and max heap.\n2) the max of max heap should be less than or equal to min of min heap.\n3) keep the heaps balanced(only diff of 1 unit is allowed).***\n```\nclass MedianFinder {\npublic:\n    // we will use heaps (min and max) to get the median using . We will try to keep them balanced on basis of their size so that at    end we will have the medians at top.\n    // we are not interested in other numbers just the middle one thats why using heap combo of min and max .\n\t// we are using min and max beacuse we will maintain our heaps in a way that max of max heap will always be lesser than equal to min of min Heap in this way we be able to get the medians\n    priority_queue<int,vector<int>,greater<int>> minH;\n    priority_queue<int> maxH;\n    MedianFinder() {}\n    \n    void addNum(int num) {\n        // we are trying to maintain a stream i.e., maxH.top() <= minH.top() in that way only we can assure the medians\n        if(maxH.empty() || num<maxH.top()){\n            maxH.push(num);\n        }\n        // incase we encounter greater number than the one present in maxH we need to add it in minH \n        else{\n            minH.push(num);\n        }\n        // we are trying to balance our heaps the max diff of size can be only 1\n        // therefore popping the extra from that heap and pushing that in the other one\n        if(maxH.size()>minH.size()+1){\n            minH.push(maxH.top());\n            maxH.pop();\n        }\n        else if(minH.size()>maxH.size()+1){\n            maxH.push(minH.top());\n            minH.pop();\n        }\n    }\n    \n    double findMedian() {\n        // this operation is going to be O(1)\n        // incase of even entries\n        if(maxH.size() == minH.size()){\n            // we will find mean of middle 2 entries and return \n            return (maxH.top() + minH.top()) / 2.0;\n        }\n        // incase of odd entries:\n        // our median will be present in that heap which has greater size\n        else{\n            return maxH.size() > minH.size() ? maxH.top() : minH.top();\n        }\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```\n**Please do upvote guys that helps me to post more solutions like this.**
['Heap (Priority Queue)']