C++ || min and max heap || fast (283ms, 100%?)
Approach 1: min heap and max heap (283ms, 100%?)\n\nThis approach uses a min and a max heap to keep track of the elements that are above and below the median an
# Approach 1: min heap and max heap (283ms, 100%?)\n\nThis approach uses a min and a max heap to keep track of the elements that are above and below the median and we rebalance them to keep them the same size. Strictly speaking we maintain the following invariant: **The "above" heap is the same size as the "below" heap or one bigger.**\n\n```cpp\nclass MedianFinder {\nprivate:\n    priority_queue<int, vector<int>, greater<int>> above_;\n    priority_queue<int> below_;\n\npublic:\n    MedianFinder() = default;\n    \n    void addNum(int num) {\n        if (empty(above_) || num >= above_.top()) {\n            above_.push(num);\n            if (size(above_) > size(below_) + 1) {\n                below_.push(above_.top());\n                above_.pop();\n            }\n        } else {\n            below_.push(num);\n            if (size(below_) > size(above_)) {\n                above_.push(below_.top());\n                below_.pop();\n            }\n        }\n    }\n    \n    double findMedian() const {\n        if (size(below_) == size(above_))\n            return 0.5 * (below_.top() + above_.top());\n        \n        return above_.top();\n    }\n};\n```\n\nTo speed up IO, I always add a line like the following to my code:\n\n```cpp\nstatic int fast_io = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();\n```\n\n**Complexity Analysis**\n  * Time Complexity: $$O(n \\log n)$$ for the push and pop operations on the heaps.\n  * Space Complexity: $$O(n)$$ for the two heaps\n\n_As always: Feedback, questions, and comments are welcome. Leaving an up-vote sparks joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['C']