A heap data structure that allows efficient merging of two heaps into one. See http://en.wikipedia.org/wiki/Binomial_heap
Python, 167 lines
Download
Copy to clipboard1 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()
|
Tags: algorithms
