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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
| class ItemRef(object):
"""Reference to an item in the heap. Used for decreasing keys and deletion.
Do not use this class directly; only use instances returned by
BinomialHeap.insert()!
You should only use ItemRef.delete() and ItemRef.decrease(new_priority).
"""
def __init__(self, node, get_heap):
self.ref = node
self.get_heap = get_heap
self.in_tree = True
def __str__(self):
if self.in_tree:
return "<BinomialHeap Reference to '%s'>" % str(self.ref.val)
else:
return "<stale BinomialHeap Reference>"
def decrease(self, new_key):
"Update the priority of the referenced item to a lower value."
assert self.in_tree
assert self.ref.ref == self
self.ref.decrease(new_key)
def delete(self):
"""Remove the referenced item from the heap.
"""
self.decrease(self)
v = self.get_heap().extract_min()
assert not self.in_tree
assert v is self.ref.val
def in_heap(self, heap):
"""Returns True if the referenced item is part of the BinomialHeap 'heap';
False otherwise.
"""
return self.in_tree and self.get_heap() == heap
def __lt__(self, other):
"Behaves like negative infinity: always True."
return True
def __gt__(self, other):
"Behaves like negative infinity: always False."
return False
class BinomialHeap(object):
"""Usage:
> H1 = BinomialHeap()
> H1.insert(40, "fast.")
> H1.insert(10, "Merging")
> H2 = BinomialHeap([(30, "quite"), (20, "is")])
> H1 += H2
> for x in H1:
> print x,
=> "Merging is quite fast."
"""
class Node(object):
"Internal node of the heap. Don't use directly."
def __init__(self, get_heap, key, val=None):
self.degree = 0
self.parent = None
self.next = None
self.child = None
self.key = key
self.ref = ItemRef(self, get_heap)
if val == None:
val = key
self.val = val
def __str__(self):
k = lambda x: str(x.key) if x else 'NIL'
return '(%s, c:%s, n:%s)' % (k(self), k(self.child), k(self.next))
def link(self, other):
"Makes other a subtree of self."
other.parent = self
other.next = self.child
self.child = other
self.degree += 1
def decrease(self, new_key):
node = self
assert new_key < node.key
node.key = new_key
cur = node
parent = cur.parent
while parent and cur.key < parent.key:
parent.ref.ref, cur.ref.ref = cur, parent
parent.ref, cur.ref = cur.ref, parent.ref
parent.key, cur.key = cur.key, parent.key
parent.val, cur.val = cur.val, parent.val
cur = parent
parent = cur.parent
@staticmethod
def roots_merge(h1, h2):
"""Merge two lists of heap roots, sorted by degree.
Returns the new head.
"""
if not h1:
return h2
if not h2:
return h1
if h1.degree < h2.degree:
h = h1
h1 = h.next
else:
h = h2
h2 = h2.next
p = h
while h2 and h1:
if h1.degree < h2.degree:
p.next = h1
h1 = h1.next
else:
p.next = h2
h2 = h2.next
p = p.next
if h2:
p.next = h2
else:
p.next = h1
return h
@staticmethod
def roots_reverse(h):
"""Reverse the heap root list.
Returns the new head. Also clears parent references.
"""
if not h:
return None
tail = None
next = h
h.parent = None
while h.next:
next = h.next
h.next = tail
tail = h
h = next
h.parent = None
h.next = tail
return h
class __Ref(object):
def __init__(self, h):
self.heap = h
self.ref = None
def get_heap_ref(self):
if not self.ref:
return self
else:
self.ref = self.ref.get_heap_ref()
return self.ref
def get_heap(self):
return self.get_heap_ref().heap
def __init__(self, lst=[]):
"""Populate a new heap with the (key, value) pairs in 'lst'.
If the elements of lst are not subscriptable, then they are treated as
opaque elements and inserted into the heap themselves.
"""
self.head = None
self.size = 0
self.ref = BinomialHeap.__Ref(self)
for x in lst:
try:
self.insert(x[0], x[1])
except TypeError:
self.insert(x)
def insert(self, key, value=None):
"""Insert 'value' in to the heap with priority 'key'. If 'value' is omitted,
then 'key' is used as the value.
Returns a reference (of type ItemRef) to the internal node in the tree.
Use this reference to delete the key or to change its priority.
"""
n = BinomialHeap.Node(self.ref.get_heap, key, value)
self.__union(n)
self.size += 1
return n.ref
def union(self, other):
"""Merge 'other' into 'self'. Returns None.
Note: This is a destructive operation; 'other' is an empty heap afterwards.
"""
self.size = self.size + other.size
h2 = other.head
self.__union(h2)
other.ref.ref = self.ref
other.__init__()
def min(self):
"""Returns the value with the minimum key (= highest priority) in the heap
without removing it, or None if the heap is empty.
"""
pos = self.__min()
return pos[0].val if pos else None
def extract_min(self):
"""Returns the value with the minimum key (= highest priority) in the heap
AND removes it from the heap, or None if the heap is empty.
"""
pos = self.__min()
if not pos:
return None
else:
(x, prev) = pos
if prev:
prev.next = x.next
else:
self.head = x.next
kids = BinomialHeap.Node.roots_reverse(x.child)
self.__union(kids)
x.ref.in_tree = False
self.size -= 1
return x.val
def __nonzero__(self):
"""True if the heap is not empty; False otherwise."""
return self.head != None
def __iter__(self):
"""Returns a _destructive_ iterator over the values in the heap.
This violates the iterator protocol slightly, but is very useful.
"""
return self
def __len__(self):
"""Returns the number of items in this heap."""
return self.size
def __setitem__(self, key, value):
"""Insert.
H[key] = value is equivalent to H.insert(key, value)
"""
self.insert(key, value)
def __iadd__(self, other):
"""Merge.
a += b is equivalent to a.union(b).
"""
self.union(other)
return self
def next(self):
"""Returns the value with the minimum key (= highest priority) in the heap
AND removes it from the heap; raises StopIteration if the heap is empty.
"""
if self.head:
return self.extract_min()
else:
raise StopIteration
def __contains__(self, ref):
"""Test whether a given reference 'ref' (of ItemRef) is in this heap.
"""
if type(ref) != ItemRef:
print("TypeError Expected an ItemRef")
else:
return ref.in_heap(self)
def __min(self):
if not self.head:
return None
min = self.head
min_prev = None
prev = min
cur = min.next
while cur:
if cur.key < min.key:
min = cur
min_prev = prev
prev = cur
cur = cur.next
return (min, min_prev)
def __union(self, h2):
if not h2:
return
h1 = self.head
if not h1:
self.head = h2
return
h1 = BinomialHeap.Node.roots_merge(h1, h2)
prev = None
x = h1
next = x.next
while next:
if x.degree != next.degree or \
(next.next and next.next.degree == x.degree):
prev = x
x = next
elif x.key <= next.key:
x.next = next.next
x.link(next)
else:
if not prev:
h1 = next
else:
prev.next = next
next.link(x)
x = next
next = x.next
self.head = h1
def heap(lst=[]):
"""Create a new heap. lst should be a sequence of (key, value) pairs.
Shortcut for BinomialHeap(lst)
"""
return BinomialHeap(lst)
|