-
Notifications
You must be signed in to change notification settings - Fork 3
/
runningMedianHeap.py
112 lines (92 loc) · 3.05 KB
/
runningMedianHeap.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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class MinHeap(object):
def __init__(self):
self.heap = []
def insert(self, k):
self.heap.append(k)
len_heap = len(self.heap)
for i in xrange(len_heap//2, -1, -1):
self.__min_heapify(i, len_heap)
def __min_heapify(self, root, len_heap):
left = 2 * root + 1
right = 2 * root + 2
smallest = root
if left <= len_heap-1 and self.heap[left] < self.heap[root]:
smallest = left
if right <= len_heap-1 and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != root:
self.heap[root], self.heap[smallest] = self.heap[smallest], self.heap[root]
self.__min_heapify(smallest, len_heap)
def remove(self):
x = self.heap.pop(0)
len_heap = len(self.heap)
for i in xrange(len_heap//2, -1, -1):
self.__min_heapify(i, len_heap)
return x
def getMin(self):
return self.heap[0]
def __len__(self):
return len(self.heap)
def printHeap(self):
return self.heap
class MaxHeap(object):
def __init__(self):
self.heap = []
def insert(self, k):
self.heap.append(k)
len_heap = len(self.heap)
for i in xrange(len_heap//2, -1, -1):
self.__max_heapify(i, len_heap)
def __max_heapify(self, root, len_heap):
left = 2 * root + 1
right = 2 * root + 2
largest = root
if left <= len_heap-1 and self.heap[left] > self.heap[root]:
largest = left
if right <= len_heap-1 and self.heap[right] > self.heap[largest]:
largest = right
if largest != root:
self.heap[root], self.heap[largest] = self.heap[largest], self.heap[root]
self.__max_heapify(largest, len_heap)
def remove(self):
x = self.heap.pop(0)
len_heap = len(self.heap)
for i in xrange(len_heap//2, -1, -1):
self.__max_heapify(i, len_heap)
return x
def getMax(self):
return self.heap[0]
def __len__(self):
return len(self.heap)
def printHeap(self):
return self.heap
def runningMedian(inp):
effectiveMedian = 0
minH = MinHeap()
maxH = MaxHeap()
for i in inp:
if i > effectiveMedian:
minH.insert(i)
else:
maxH.insert(i)
# re balance the heaps
lenMinHeap = len(minH)
lenMaxHeap = len(maxH)
if abs(lenMinHeap-lenMaxHeap) > 1:
if lenMinHeap > lenMaxHeap:
maxH.insert(minH.remove())
else:
minH.insert(maxH.remove())
lenMinHeap = len(minH)
lenMaxHeap = len(maxH)
if lenMinHeap == lenMaxHeap:
effectiveMedian = (minH.getMin() + maxH.getMax()) / 2.0
elif lenMinHeap > lenMaxHeap:
effectiveMedian = minH.getMin()
else:
effectiveMedian = maxH.getMax()
print effectiveMedian
if __name__ == '__main__':
inp = [6, 12, 4, 5, 3, 8, 7]
inp = [5, 15, 10, 20, 3]
runningMedian(inp)