Welcome, guest | Sign In | My Account | Store | Cart

A heap data structure that allows efficient merging of two heaps into one. See http://en.wikipedia.org/wiki/Binomial_heap

Python, 167 lines
 ``` 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() ```
 Created by Irit Katriel on Tue, 1 May 2007 (PSF)

### Required Modules

• (none specified)