Leetcode - Find Median From Data Stream

Question

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

This is aheap question.

Idea(s)

• Use two heaps, a max heap and a min heap which stores numbers in sorted order of the bottom half and top half of a list
  • We use two heaps so we can quickly index the two middle numbers to compute the median
• These heaps are approximately equal in length, if they are not, we need to remove the max value from the “small heap / max heap” and put it into the “large heap / min heap”
• We need to also make sure the small heap has values ≤ to the large heap, if a value in small heap is not ≤ the min value in the large heap, we need to also remove the max value from the “small heap / max heap” and put it into the “large heap / min heap”
• Implementation details
  • The class requires the two heaps
  • heapq is the python class used to implement a min heap
    • This uses heappop and heappush
  • to implement a max heap, multiply added numbers by -1

Solution