Find Median from Data Stream

Find Median from Data Stream Design a data structure that receives a stream of integers and supports: addNum(num): Add integer num to the stream. findMedian(): Return the median of all numbers seen so far. Median definition: If the number of elements is odd, return the middle element after sorting. If it is even, return the average of the two middle elements. Target complexity: O(log n) per addNum and O(1) per findMedian. Example addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2.0 Follow-ups How would you optimize if the value range is very small? How would you support finding the k-th smallest element instead of the median? Example Input add 1 add 2 median Output 1.5