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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170 | """
BinomialQueue.py
Meldable priority queues
Written by Gregoire Dooms and Irit Katriel
"""
class LinkError(Exception): pass
class EmptyBinomialQueueError(Exception): pass
class BinomialTree:
"A single Binomial Tree"
def __init__(self, value):
"Create a one-node tree. value is the priority of this node"
self.value = value
self.rank = 0
self.children = []
def link(self, other_tree):
"""Make other_tree the son of self. Both trees must have the
same rank, and other_tree must have a larger minimum priority
"""
if self.rank != other_tree.rank:
raise LinkError()
if self.value > other_tree.value:
raise LinkError()
self.children.append(other_tree)
self.rank += 1
return True
def str(self, indent = 0):
return (" "*indent +
"rank: %d value: %d"%(self.rank, self.value)+
"\n"+"".join(child.str(indent+2)
for child in self.children)
)
def __str__(self):
return self.str()
class BinomialQueue:
""" A Meldable priority Queue """
def __init__(self,infinity=1e300):
"""
Create an empty Binomial Queue.
Since a queue can hold any comparable data type, we need to know
at initialization time what an "infinity" element looks like.
"""
self.infinity = infinity
self.parent = self
self.trees = []
self.elements = 0
self.min = self.infinity
self.min_tree_rank = -1
def __capacity(self):
return 2**len(self.trees) - 1
def __resize(self):
while self.__capacity() < self.elements:
self.trees.append(None)
def __add_tree(self,new_tree):
" Insert new_tree into self"
self.elements = self.elements + 2**new_tree.rank
self.__resize()
while self.trees[new_tree.rank] is not None:
if self.trees[new_tree.rank].value < new_tree.value:
new_tree, self.trees[new_tree.rank] = \
self.trees[new_tree.rank], new_tree # swap
r = new_tree.rank
new_tree.link(self.trees[r])
self.trees[r] = None
self.trees[new_tree.rank] = new_tree
if new_tree.value <= self.min:
self.min = new_tree.value
self.min_tree_rank = new_tree.rank
def meld(self, other_queue):
"Insert all elements of other_queue into self "
for tree in other_queue.trees:
if tree is not None:
self.__add_tree(tree)
def insert(self, value):
"Insert value into self "
tree = BinomialTree(value)
self.__add_tree(tree)
def get_min(self):
"Return the minimum element in self"
return self.min
def delete_min(self):
"Delete the minumum element from self "
if not self:
raise EmptyBinomialQueueError()
to_remove = self.trees[self.min_tree_rank]
self.trees[to_remove.rank] = None
self.elements = self.elements - 2**to_remove.rank
for child in to_remove.children:
self.__add_tree(child)
self.min = self.infinity
for tree in self.trees:
if tree is not None:
if tree.value <= self.min:
self.min = tree.value
self.min_tree_rank = tree.rank
def __nonzero__(self):
return self.elements
def __str__(self):
s = """elements: %d min: %s
min_tree_rank: %d
tree vector: """ % (self.elements, str(self.min), self.min_tree_rank)
s += " ".join("10"[tree is None] for tree in self.trees)
s += "\n"
s += "".join(str(tree) for tree in self.trees if tree is not None)
return s
def __len__(self):
return self.elements
def __iadd__(self,other):
if type(other) == type(self):
self.meld(other)
else:
self.insert(other)
return self
def run_test():
inf = 2e300
N = 10
Q1 = BinomialQueue(inf)
Q2 = BinomialQueue(inf)
print Q1
print "-------------------------------------------"
Q1 += 20 # Same as Q1.insert(20)
Q1.insert(1)
Q1.insert(5)
Q1.insert(10)
print Q1
print "-------------------------------------------"
Q2.insert(2)
Q2.insert(22)
Q2.insert(12)
print Q2
print "-------------------------------------------"
Q1 += Q2 # Same as Q1.meld(Q2)
print Q1
print "-------------------------------------------"
while Q1:
print "Q1.min = ", Q1.min
Q1.delete_min()
if __name__ == "__main__":
run_test()
|
Sign in to comment