C++ | Explained in Detail | Heaps | Priority Queue | O(logN)
\n/* \nHarshit Gupta | 24th May, 2021\n\nC++ program for finding median in a running stream of integers.\n\nhttps://leetcode.com/problems/find-median-from-data-
```\n/* \nHarshit Gupta | 24th May, 2021\n\nC++ program for finding median in a running stream of integers.\n\nhttps://leetcode.com/problems/find-median-from-data-stream/\n\nSolution: \n    a.  Create two heaps. One max heap to maintain elements of lower half \n        and one min heap to maintain elements of higher half at any point of time.\n    b.  Take initial value of median as 0.\n    c.  For every newly read element, insert it into either max heap or min heap \n        and then calulate the median based on the following conditions:\n        - If the size of max heap is greater than size of min heap and the \n            element is less than previous median then pop the top element from \n            max heap and insert into min heap and insert the new element to max \n            heap else insert the new element to min heap. Calculate the new median \n            as average of top of elements of both max and min heap.\n        - If the size of max heap is less than size of min heap and the element \n            is greater than previous median then pop the top element from min heap \n            and insert into max heap and insert the new element to min heap else \n            insert the new element to max heap. Calculate the new median as average \n            of top of elements of both max and min heap.\n        - If the size of both heaps are same. Then check if current is less than \n            previous median or not. If the current element is less than previous \n            median then insert it to max heap and new median will be equal to top \n            element of max heap. If the current element is greater than previous \n            median then insert it to min heap and new median will be equal to top \n            element of min heap.\n\nParadigm: Priority Queues, Heaps.\n\nTime Complexity: O(nlogn) to balance the heaps/heapify.\n\n*/\n\n\n\nclass MedianFinder {\npublic:\n    // max heap to store the smaller half elements\n    priority_queue<int> max_heap;\n    \n    // min heap to store the greater half elements \n    priority_queue<int, vector<int>, greater<int>> min_heap;\n    \n    // Variable which will contain the median value at all instance of time.\n    // We can return it in O(1) time.\n    double median;\n    \n    MedianFinder() {\n        // initializing the median to 0\n        median = 0;\n    }\n    \n    void addNum(int num) {\n        \n        // Case 1: Left side heap has more elements\n        // Pushing an element would have EVEN number of elements in total, \n        // so median is average of top of min and max heaps\n        \n        // If the size of max heap(s) is greater than the min heap(g)\n        if(max_heap.size() > min_heap.size()) {\n            \n            // And the element is lesser than the median, then it has to be inserted in the max heap\n            // But if directly inserted it will create imbalance in both heaps, \n            // so the maximum(top) of max heap(s) is moved to the min heap(g)\n            // and then the element is inserted to the max heap.\n            if(num < median) {\n                // Insert the top of max heap to min heap\n                min_heap.push(max_heap.top());\n                // Remove the top element of the max heap.\n                max_heap.pop();\n                // Insert the new element in the min heap\n                max_heap.push(num);\n            }\n            // And the element is greater then the current median\n            else{\n                // Push it in the min heap. Now both heaps has equal elements.\n                min_heap.push(num);\n            }\n            \n            median = (double)(min_heap.top() + max_heap.top()) / 2.0;\n        }\n        \n        // Case 2: Right side heap has more elements.\n        // Pushing an element would have EVEN number of elements in total, \n        // so median is average of top of min and max heaps\n        \n        // If the size of max heap(s) is lesser than the min heap(g). \n        else if (max_heap.size() < min_heap.size()){\n            \n            // And the element is greater than the median, then it has to be inserted in the min heap\n            // But if directly inserted it will create imbalance in both heaps, \n            // so the minimum(top) of min heap(g) is moved to the max heap(s)\n            // and then the element is inserted to the min heap.\n            if(num > median){\n                // Insert the top of min heap to the max heap.\n                max_heap.push(min_heap.top());\n                // Remove the top element of min heap since it is already inserted in the max heap\n                min_heap.pop();\n                // Insert the new element in the max heap.\n                min_heap.push(num);\n            }\n            // And the element is less than the current median\n            else{\n                // Push it in the max heap. Now both heaps has equal elements.\n                max_heap.push(num);\n            }\n            \n            median = (double)(min_heap.top() + max_heap.top()) / 2.0;\n        }\n        \n        // Case 3: Both heaps have equal elements and are balanced.\n        // If both the heaps has equal elements, then inserting this element \n        // would make the heaps have \'ODD\' number of elements and thus the median now\n        // would be only one number and not average of two numbers.\n        else {\n            // If the element is less than the current median, it is inserted in the max heap\n            // and now since max heap has more elements, the top of max heap would be the median.\n            if( num < median){\n                max_heap.push(num);\n                median = (double)max_heap.top();\n            }\n            // If the element is greater than the current median, it is inserted in the min heap\n            // and now since min heap has more elements, the top of min heap would be the median.\n            else{\n                min_heap.push(num);\n                median = (double)min_heap.top();\n            }\n        }\n        \n    }\n    \n    double findMedian() {\n        return median;\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```
['C', 'Heap (Priority Queue)', 'C++']