You are viewing a single comment's thread. Return to all comments →
My Python 3 implementation using two heaps. A little bit tedious if/else though ...
#!/bin/python3 import sys import heapq n = int(input().strip()) a = [] min_heap = [] max_heap = [] len_min_heap = 0 len_max_heap = 0 a_i = 0 for a_i in range(n): a_t = int(input().strip()) if a_i == 0: heapq.heappush(max_heap, -1*a_t) heapq.heappush(min_heap, a_t) print(float(a_t)) elif a_i == 1: if a_t > min_heap[0]: heapq.heapreplace(min_heap, a_t) else: heapq.heapreplace(max_heap, -1*a_t) print((min_heap[0] - max_heap[0])/2) len_min_heap = 1 len_max_heap = 1 else: if len_min_heap == len_max_heap: if -1 * a_t < max_heap[0]: heapq.heappush(min_heap, a_t) len_min_heap += 1 print(float(min_heap[0])) else: heapq.heappush(max_heap, -1*a_t) len_max_heap += 1 print(float(-1 * max_heap[0])) elif len_min_heap > len_max_heap: if a_t > min_heap[0]: heapq.heappush(min_heap, a_t) heapq.heappush(max_heap, -1*heapq.heappop(min_heap)) else: heapq.heappush(max_heap, -1*a_t) len_max_heap += 1 print((min_heap[0]-max_heap[0])/2) else: if -1 * a_t > max_heap[0]: heapq.heappush(max_heap, -1 * a_t) heapq.heappush(min_heap, -1*heapq.heappop(max_heap)) else: heapq.heappush(min_heap, a_t) len_min_heap += 1 print((min_heap[0]-max_heap[0])/2) a.append(a_t)
Seems like cookies are disabled on this browser, please enable them to open this website
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
My Python 3 implementation using two heaps. A little bit tedious if/else though ...