You are viewing a single comment's thread. Return to all comments →
Here's the DIY version, if anyone's interested:
#!/bin/python3 import sys def siftdown(heap): c = len(heap) - 1 p = (c - 1) >> 1 while c > 0 and heap[c] < heap[p]: temp = heap[c] heap[c] = heap[p] heap[p] = temp c = p p = (c - 1) >> 1 def siftup(heap): p = 0 while 2*p+1 < len(heap): c = 2*p+1 if c+1 < len(heap) and heap[c] > heap[c+1]: c += 1 if heap[p] > heap[c]: temp = heap[p] heap[p] = heap[c] heap[c] = temp p = c else: break up = [] down = [] n = int(input().strip()) a_i = 0 for a_i in range(n): a_t = int(input().strip()) if not up: up.extend([a_t]) elif a_t > up[0]: up.extend([a_t]) siftdown(up) else: down.extend([-a_t]) siftdown(down) if len(up) < len(down): up.extend([-down[0]]) siftdown(up) down[0] = down[-1] down.pop() siftup(down) elif len(up) > len(down) + 1: down.extend([-up[0]]) siftdown(down) up[0] = up[-1] up.pop() siftup(up) if (len(up) + len(down)) % 2 == 0: print('%.1f' % round((up[0]-down[0])/2, 1)) else: print('%.1f' % up[0])
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 →
Here's the DIY version, if anyone's interested: