Welcome, guest | Sign In | My Account | Store | Cart
```"""
BinomialQueue.py
Meldable priority queues
Written by Gregoire Dooms and Irit Katriel
"""

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 = []

"""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:
if self.value > other_tree.value:
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)

" 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
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:

def insert(self, value):
"Insert value into self "
tree = BinomialTree(value)

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.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

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()

```