-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheap.py
More file actions
executable file
·119 lines (99 loc) · 3.18 KB
/
heap.py
File metadata and controls
executable file
·119 lines (99 loc) · 3.18 KB
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
113
114
115
116
117
118
119
#!/usr/bin/python -B
'''
Created on Jul 14, 2013
@author: Bill Dimmick <[email protected]>
'''
'''
Functional comparitor for minimal heap building
'''
def minheap(a, b):
return a < b
'''
Functional comparitor for maximal heap building
'''
def maxheap(a, b):
return a > b
class Heap(object):
def __init__(self, comp=maxheap):
self.values=[]
self.comparator = comp
def __parent__(self, i):
return i // 2
def __left__(self, i):
return (i * 2) + 1
def __right__(self, i):
return (i + 1) * 2
def __add__(self, other):
result = Heap()
result.values.extend(self.values)
result+=other
return result
def __contains__(self, i):
return i in self.values
def __heapify__(self, i):
left = self.__left__(i)
right = self.__right__(i)
bound = len(self.values)
largest = i
if (left < bound) and (self.comparator(self.values[left], self.values[largest])):
largest = left
if (right < bound) and (self.comparator(self.values[right], self.values[largest])):
largest = right
if largest is not i:
self.__swap__(i, largest)
self.__heapify__(largest)
def __iadd__(self, other):
if type(other)==Heap:
for val in other.values:
self.append(val)
elif '__iter__' in dir(other):
for val in other:
self.append(val)
else:
self.append(other)
return self
def __len__(self):
return len(self.values)
def __swap__(self, i, j):
v = self.values[i]
self.values[i] = self.values[j]
self.values[j] = v
def append(self, obj):
self.values.append(obj)
i = len(self.values) - 1
parent = self.__parent__(i)
while (i > 0) and (self.comparator(self.values[i], self.values[parent])):
self.__swap__(i, parent)
i = parent
parent = self.__parent__(i)
def drain(self, until = None, filt = None):
result = []
if until:
skipped = []
while (until(self.values[0])):
val = self.pop()
if filt:
if (filt(val)):
result.append(val)
else:
skipped.append(val)
else:
result.append(val)
for k in skipped:
self.append(k)
else:
if not filt:
filt = lambda a: True
while len(self.values) > 0:
val = self.pop()
if filt(val):
result.append(val)
return result
def pop(self):
if (len(self.values) > 0):
result = self.values[0]
end = len(self.values) - 1
self.values[0] = self.values[end]
self.values = self.values[0:end]
self.__heapify__(0)
return result