-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathMinTree.py
executable file
·43 lines (40 loc) · 1.81 KB
/
MinTree.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
# A tree data structure which stores a list of degrees and can quickly retrieve the min degree element,
# or modify any of the degrees, each in logarithmic time. It works by creating a binary tree with the
# given elements in the leaves, where each internal node stores the min of its two children.
import math
class MinTree:
def __init__(self, degrees):
self.height = int(math.ceil(math.log(len(degrees), 2)))
self.numLeaves = 2 ** self.height
self.numBranches = self.numLeaves - 1
self.n = self.numBranches + self.numLeaves
self.nodes = [float('inf')] * self.n
for i in range(len(degrees)):
self.nodes[self.numBranches + i] = degrees[i]
for i in reversed(list(range(self.numBranches))):
self.nodes[i] = min(self.nodes[2 * i + 1], self.nodes[2 * i + 2])
# @profile
def getMin(self):
cur = 0
for i in range(self.height):
cur = (2 * cur + 1) if self.nodes[2 * cur + 1] <= self.nodes[2 * cur + 2] else (2 * cur + 2)
# print "found min at %d: %d" % (cur, self.nodes[cur])
return (cur - self.numBranches, self.nodes[cur])
# @profile
def changeVal(self, idx, delta):
cur = self.numBranches + idx
self.nodes[cur] += delta
for i in range(self.height):
cur = (cur - 1) // 2
nextParent = min(self.nodes[2 * cur + 1], self.nodes[2 * cur + 2])
if self.nodes[cur] == nextParent:
break
self.nodes[cur] = nextParent
def dump(self):
print("numLeaves: %d, numBranches: %d, n: %d, nodes: " % (self.numLeaves, self.numBranches, self.n))
cur = 0
for i in range(self.height + 1):
for j in range(2 ** i):
print(self.nodes[cur], end=' ')
cur += 1
print('')