Median Finder with Two Heaps

Problem

Simulate a data structure that supports adding numbers and querying the median.

operations contains "add" (values[i] is the number) or "find_median" (values[i] is ignored). Keep a max-heap for the lower half and a min-heap for the upper half, rebalancing so their sizes differ by at most one. find_median returns the middle value, or the average of the two middle values as a float, or None when empty.

Return the list of recorded results.

Hint

Push to the max-heap, move its top to the min-heap, then rebalance if the min-heap grew larger.

Test cases

case 1

in: [["add","add","find_median","add","find_median"],[1,2,0,3,0]]

expected: [null,null,1.5,null,2]

case 2

in: [["find_median"],[0]]

expected: [null]

case 3

in: [["add","find_median"],[5,0]]

expected: [null,5]

case 4

in: [["add","add","add","find_median"],[2,1,3,0]]

expected: [null,null,null,2]

Starter codePython

def median_finder(operations, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor