Solution: Find Median from Data Stream

Statement

Create a data structure that can store a list of integers that can change in size over time and find the median from this dynamically growing list in constant time, $O(1)$.

Implement a struct, MedianOfStream, which should provide the following functionalities:

1. Init(): Initializes the data structure, setting up the necessary components to manage the stream of integers, i.e., it creates the max and the min heap.

2. Insert Num(num): Adds an integer, num, to the data structure.

3. Find Median(): Finds the median of all elements seen so far. If there are an even number of elements, return the average of the two middle values.

Constraints:

• $-10^5 \leq$ num $\leq 10^5$, where num is an integer received from the data stream.

• There will be at least one element in the data structure before the median is computed.

• At most, $500$ calls will be made to the function that calculates the median.