median_integer_stream.py 文件源码

def median_stream_ints(arr):

    less_than_med = []
    greater_than_med = []

    for i in range(len(arr)):
        print 'Median after adding:', arr[i]
        if len(less_than_med) == 0 and len(greater_than_med) == 0:
            heapq.heappush(less_than_med, -arr[i])  # max-heap in Python implemented by negation.
        elif arr[i] < abs(less_than_med[0]):
            heapq.heappush(less_than_med, -arr[i])
            if len(less_than_med) - len(greater_than_med) > 1:
                root = abs(heapq.heappop(less_than_med))
                heapq.heappush(greater_than_med, root)
        elif len(greater_than_med) == 0 or arr[i] > greater_than_med[0]:
            heapq.heappush(greater_than_med, arr[i])
            if len(greater_than_med) - len(less_than_med) > 1:
                root = heapq.heappop(greater_than_med)
                heapq.heappush(less_than_med, -root)
        if len(less_than_med) == len(greater_than_med):
            print (greater_than_med[0] - less_than_med[0]) / 2
        else:
            print abs(less_than_med[0]) if len(less_than_med) > len(greater_than_med) else greater_than_med[0]