class BinomialHeapNode: def __init__(self, key): self.key = key self.parent = None self.degree = 0 self.child = None self.sibling = None class BinomialHeap: def __init__(self): self.head = None def make_heap(): return BinomialHeap() def make_node(key): return BinomialHeapNode(key) def is_empty(H): return H.head == None def minimum(H): y = H.head if y != None: min = y.key x = y.sibling while x != None: if x.key < min: min = x.key y = x x = x.sibling return y def __link(x, y): x.sibling = y.child x.parent = y y.child = x y.degree = y.degree + 1 def __merge(Hx, Hy): class SiblingWrapper: sibling = None x = Hx.head y = Hy.head h = SiblingWrapper() # head t = h # tail while x != None and y != None: if x.degree <= y.degree: t.sibling = x t = x x = x.sibling else: t.sibling = y t = y y = y.sibling if x != None: t.sibling = x else: t.sibling = y return h.sibling def __union(H1, H2): H = BinomialHeap() H.head = __merge(H1, H2) if H.head == None: return H w = None x = H.head while x.sibling != None: if x.degree != x.sibling.degree or (x.sibling.sibling != None and x.sibling.sibling.degree == x.degree): w = x x = x.sibling else: if x.key <= x.sibling.key: y = x.sibling z = y.sibling x.sibling = z __link(y, x) else: y = x.sibling if w != None: w.sibling = y else: H.head = y __link(x, y) x = y return H def __print_siblings(x): while x != None: f1.write(x.degree) x = x.sibling def insert(H, x): S = BinomialHeap() S.head = x T = __union(H, S) H.head = T.head def extract(H): if H.head == None: return None prev = None min = H.head w = min x = min.sibling while x != None: if x.key < min.key: prev = w min = x w = x x = x.sibling if prev != None: assert(prev.sibling == min) prev.sibling = min.sibling else: assert(H.head == min) H.head = min.sibling S = BinomialHeap() x = min.child while x != None: x.parent = None y = x.sibling # save the next child x.sibling = S.head S.head = x x = y # Union S with H and update H.head. T = __union(H, S) H.head = T.head # Clean up min and return it. min.sibling = None min.child = None min.degree = 0 min.parent = None return min def decrease_key(H, x, k): assert(k <= x.key) if k == x.key: return # do nothing x.key = k y = x z = y.parent while z != None and y.key < z.key: #print "Swapping %d and %d." % (y.key, z.key) y.key, z.key = z.key, y.key y = z z = y.parent def delete(H, x): min = minimum(H) decrease_key(H, x, min.key-1) extract(H) def print_heap(x, indent='#', char='#'): while x != None: f1.write( "%s %d [%d]" %(indent, x.key, x.degree)) if x.child != None: print_heap(x.child, indent+char, char) x = x.sibling f=open('in_sec_21_16.txt','r') f1=open('out_16_sec21_6.txt','w') dat=f.readline() data=dat.split(",") f1.write("INPUT DATA:") f1.write(dat) f1.write("\n") for i in range(0,len(data)): data[i]=int(data[i]) min = None max = None nodes = [] H = BinomialHeap() for d in data: f1.write("\nINSERT (%2d)\n"%(d)) n = BinomialHeapNode(d) if min == None or n.key < min.key: min = n if max == None or n.key > max.key: max = n nodes.append(n) insert(H, n) print_heap(H.head, '\no', '->') f1.write("\nmin.key = %d, max.key = %d\n" % (min.key, max.key)) for i in xrange(len(data)/2): n = extract(H) d = n.key f1.write("\nEXTRACTED (%2d)\n"%(d)) print_heap(H.head, '\no', '->') f.close() f1.close()