-
Notifications
You must be signed in to change notification settings - Fork 85
/
median_maintenance.py
63 lines (45 loc) · 1.7 KB
/
median_maintenance.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# Purpose of median_maintenance is given numbers, x then y, w, etc, maintain the median.
# Programmed by Aladdin Persson
# 2019-02-16 <aladdin.persson at hotmail dot com>
# This is an optimized version using heap
# note: heapq is a min-heap that is why we do -x, also we want all small values in the maxheap
# and all large values in the minheap so that we can take the value on the top as our median
# Improvements to be made:
# * Do it without the use of globals
# * Comment code
import heapq
class Maintain_Median(object):
def __init__(self):
self.maxheap = []
self.minheap = []
def medmain_insert(self, x):
if len(self.maxheap) == 0:
heapq.heappush(self.maxheap, -x)
else:
m = -self.maxheap[0]
if x > m:
heapq.heappush(self.minheap, x)
if len(self.minheap) > len(self.maxheap):
y = heapq.heappop(self.minheap)
heapq.heappush(self.maxheap, -y)
else:
heapq.heappush(self.maxheap, -x)
if len(self.maxheap) - len(self.minheap) > 1:
y = -heapq.heappop(self.maxheap)
heapq.heappush(self.minheap, y)
return (
(-self.maxheap[0] + self.minheap[0]) / 2
if len(self.maxheap) == len(self.minheap)
else -self.maxheap[0]
)
def main(self, data):
if len(data) < 1:
return data
for x in data:
median = self.medmain_insert(x)
return median
if __name__ == "__main__":
data = [1, 3, 8, 5, 10]
maintain_median = Maintain_Median()
median = maintain_median.main(data)
print(median)