$(30$ pts$.)$ Median Heaps. Consider an array of $N$ numbers $x_1,x_2,$dots,$x_N$ that you will be receiving one$-$

by$-$one in a single pass $($i$.$e$.,$ as a stream of numbers$).$ You are not allowed to re$-$query previous numbers.

Design an effective data structure involving one or more heaps that, after receiving the n$-$th number, reports

the median of the numbers $x_1,x_2,$dots,$x_n,$ observed so far. The time complexity of your algorithm should be

$O(logn)$ per number received in the worst case. For simplicity, assume there are no duplicates in the stream.

Explain the algorithm$/$data structure, running time, and correctness.

Hint: If $n$ is odd, the median of the data stream $x_1,x_2,$dots,$x_n$ is the middle element of the sorted data stream,

else the median is the average of the middle two elements of the sorted data stream.