📌📌 C++ || HEAP || Faster || Easy To Understand
Using Heap\n\n Time Complexity :- O(logN) for both add and median function\n\n Space Complexity :- O(N)\n\n\nclass MedianFinder {\npublic:\n    \n    // smaller
* ***Using Heap***\n\n* ***Time Complexity :- O(logN) for both add and median function***\n\n* ***Space Complexity :- O(N)***\n\n```\nclass MedianFinder {\npublic:\n    \n    // smaller will contain half smaller elements\n    \n    priority_queue<int> smaller;\n    \n    // larger will contain half larger elements\n    \n    priority_queue<int, vector<int>, greater<int>> larger;\n    \n    MedianFinder() {\n        \n    }\n    \n    void addNum(int num) {\n        \n        // push the num into smaller\n        \n        smaller.push(num);\n        \n        // if largest element of smaller is greater than the smallest element of larger, then push the top of smaller into larger\n        \n        if(!smaller.empty() && !larger.empty() && smaller.top() > larger.top())\n        {\n            int val = smaller.top();\n            \n            smaller.pop();\n            \n            larger.push(val);\n        }\n        \n        // if the size of smaller is greater than larger by 2 then push the top of smaller into larger\n        \n        if(smaller.size() > larger.size() + 1)\n        {\n            int val = smaller.top();\n            \n            smaller.pop();\n            \n            larger.push(val);\n        }\n        \n        // if the size of larger is greater than smaller by 2 then push the top of larger into smaller\n        \n        else if(larger.size() > smaller.size() + 1)\n        {\n            int val = larger.top();\n            \n            larger.pop();\n            \n            smaller.push(val);\n        }\n    }\n    \n    double findMedian() {\n        \n        if(smaller.size() == larger.size())\n        {\n            return (double(smaller.top()) + double(larger.top())) / 2;\n        }\n        \n        else if(smaller.size() == larger.size() + 1)\n        {\n            return double(smaller.top());\n        }\n        \n        else\n        {\n            return double(larger.top());\n        }\n    }\n};\n```
['C', 'Heap (Priority Queue)', 'C++']