[C++] Double Heap Solution Explained, ~100% Time, ~25% Space
The base idea here is to keep constanly the data received into 2 halves and keep rebalancing them as we go inserting more.\n\nTo do so, we will create 2 heaps:\
The base idea here is to keep constanly the data received into 2 halves and keep rebalancing them as we go inserting more.\n\nTo do so, we will create 2 heaps:\n* `lows` is a maxheap that will collect the lower half of the values;\n* `highs`, specularly, is a minhap that will collect the upper half.\n\nWe will do nothing in the constructor and move on with the `addNum` method, in which we will take the provided input `val` and:\n* push `val` into `lows` if `lows` had no previous elements or `val < lows.top()`;\n* push `val` into `highs` otherwise;\n* rebalance the heaps to make sure that `lows` is never smaller and their difference in size is never `> 1`, moving the currently top element from one to the other.\n\nIn the `findMedian` method we can go and, if the number of provided elements so far is odd (ie: `lows.size() > highs.size()`) we will just return `lows.tops()`, otherwise we will return the average of both `.top()`s, since they are the central values :)\n\nThe code:\n\n```cpp\nclass MedianFinder {\n    priority_queue<int> lows;\n    priority_queue<int, vector<int>, greater<int>> highs;\npublic:\n    /** initialize your data structure here. */\n    MedianFinder() {}\n    \n    void addNum(int val) {\n        // deciding in which half val goes:\n        if (lows.empty() || val < lows.top()) lows.push(val);\n        else highs.push(val);\n        // rebalancing to avoid higher becoming bigger\n        if (lows.size() < highs.size()) {\n            lows.push(highs.top());\n            highs.pop();\n        }\n        // or lows growing more than 1 element from the size of highs\n        else if (lows.size() > highs.size() + 1) {\n            highs.push(lows.top());\n            lows.pop();\n        }\n    }\n    \n    double findMedian() {\n        // computing the result depengn if we have seen odd amount of elements or not\n        return lows.size() > highs.size() ? lows.top() : (lows.top() + highs.top()) / 2.0;\n    }\n};\n```
['C', 'Heap (Priority Queue)', 'C++']