[ C++ ] Easy, Understandable ,Two heaps Intuitive Solution. O(logn) add, O(1) find
As the data stream continuously come in, we have to consider the middle most element everytime for calculating the median.\n\nTWO HEAP INTUITION : We have to co
As the data stream continuously come in, we have to consider the middle most element everytime for calculating the median.\n\n**TWO HEAP INTUITION :** **We have to consider middle element/s where all other elements are sorted as data stream come. Heaps come into picture with less time complexity to achieve this. So, we keep two heaps, one min heap and one max heap and keep a track of middle elements by balancing each heap.**\n\nThe left heap is containing elements in decreasing order (Max to Min) and right heap is in increasing order (Min to Max) but all the elements are greater than the left heap elements. We start pushing the elements in left heap and try to balance it everytime by comparing with the new elements and with heap size and accordingly put it into the right heap.\n```\nclass MedianFinder {\npublic:\n    /** initialize your data structure here. */\n    priority_queue<int, vector<int>, greater<int> > minHeap;\n\tpriority_queue<int> maxHeap;\n    MedianFinder(){}\n\n    void addNum(int num) {\n        if (maxHeap.empty() or maxHeap.top() > num) {\n\t\t\tmaxHeap.push(num);\n\t\t} else {\n\t\t\tminHeap.push(num);\n\t\t}\n\n\t\tif (maxHeap.size() > minHeap.size() + 1) {\n\t\t\tminHeap.push(maxHeap.top());\n\t\t\tmaxHeap.pop();\n\t\t} else if (minHeap.size() > maxHeap.size() + 1) {\n\t\t\tmaxHeap.push(minHeap.top());\n\t\t\tminHeap.pop();\n\t\t}\n    }\n    \n    double findMedian() {\n        if (maxHeap.size() == minHeap.size()) {\n\t\t\tif (maxHeap.empty()) {\n\t\t\t\treturn 0;\n\t\t\t} else {\n\t\t\t\tdouble avg = (maxHeap.top() + minHeap.top()) / 2.0;\n\t\t\t\treturn avg;\n\t\t\t}\n\n\t\t} else {\n\t\t\treturn maxHeap.size() > minHeap.size() ? maxHeap.top() : minHeap.top();\n\t\t}\n    }\n};\n\n```\n\nPlease upvote if you find the solution helpful :)\n
['C', 'Heap (Priority Queue)', 'C++']