Expert · Data structures · 260 of 264
Running median
After each new number, print the median of all numbers so far, with one decimal. With up to 1200 numbers, sorting each time is slow: keep two heaps.
Input: n, then n whole numbers on one line. Output: n medians on one line.
Examples
Input
4 5 15 1 3
Output
5.0 10.0 5.0 4.0
Input
1 7
Output
7.0
Input
5 1 2 3 4 5
Output
1.0 1.5 2.0 2.5 3.0
One more test checks other inputs when you press Check.
Stuck? The idea behind data structures
Choose the structure for what you do most: a heap (heapq) gives the smallest item fast, a deque adds and removes at both ends, a dictionary finds by key.
Two heaps, one for each half, keep the middle value of a stream of numbers.
import heapq
h = []
for x in [5, 1, 8, 3]:
heapq.heappush(h, x)
print(heapq.heappop(h), heapq.heappop(h)) # 1 3Watch for: heapq keeps the smallest first: for the largest, push -x and turn it back when you pop.