算法导论第十九章习题解答

import math class NODE(): def __init__(self, key): self.key = key self.left = self self.right = self self.parent = None self.child = None self.degree = 0 self.mark = False class FIB_HEAP(): def __init__(self): self.num = 0 self.min = None self.rootList = None class DL_LIST(): def __init__(self): self.nil = NODE(None) self.nil.right = self.nil self.nil.left = self.nil def DL_LIST_SEARCH(L, k): x = L.nil.right while x != L.nil and x.key != k: x = x.right return x def DL_LIST_INSERT(L, x): x.right = L.nil.right L.nil.right.left = x L.nil.right = x x.left = L.nil def DL_LIST_INSERT_BEFORE(L, x, y): y.left = x.left y.right = x x.left.right = y x.left = y def DL_LIST_DELETE(L, x): x.left.right = x.right x.right.left = x.left def DL_LIST_UNION(L1, L2): head1 = L1.nil.right tail1 = L1.nil.left head2 = L2.nil.right tail2 = L2.nil.left tail1.right = head2 head2.left = tail1 tail2.right = L1.nil L1.nil.left = tail2 L2.nil.left = None L2.nil.right = None def DL_LIST_PRINT(L): y = L.nil.right while y != L.nil: print(y.key, y.mark, y.degree) if y.child != None: print("---------child of ", y.key) DL_LIST_PRINT(y.child) print("----------child end") y = y.right def FIB_HEAP_INSERT(H, x): x.parent = None x.child = None x.degree = 0 x.mark = False if H.min == None: H.root = DL_LIST() DL_LIST_INSERT(H.root, x) H.min = x else: DL_LIST_INSERT_BEFORE(H.root, H.min, x) if x.key < H.min.key: H.min = x H.num = H.num + 1 def FIB_HEAP_UNION(H1, H2): H = FIB_HEAP() H.min = H1.min DL_LIST_UNION(H.root, H2.root) if (H1.min == None) or (H2.min != None and H2.min.key < H1.min.key): H.min = H2.min H.num = H1.num + H2.num H1.root = None H1.min = None H2.root = None H2.min = None return H def FIB_HEAP_EXTRACT_MIN(H): z = H.min if z != None: if z.child != None: x = z.child.nil.right while x != z.child.nil: x.parent = None y = x.right DL_LIST_INSERT_BEFORE(H.root, H.min, x) x = y DL_LIST_DELETE(H.root, z) if H.root.nil.right == H.root.nil and H.root.nil.left == H.root.nil: H.min = None else: H.min = z.right CONSOLIDATE(H) H.num = H.num -1 return z def D(num): return int(math.log(num, 2))+1 def CONSOLIDATE(H): A = [None for i in range(D(H.num)+1)] w = H.min last = w.left flag = True while flag: x = w w = w.right if x == H.root.nil: continue elif x == last: flag = False d = x.degree while A[d] != None: y = A[d] if x.key > y.key: temp = x x = y y = temp FIB_HEAP_LINK(H, y, x) A[d] = None d = d + 1 A[d] = x H.min = None for i in range(0, D(H.num)+1): if A[i] != None: if H.min == None: H.root = DL_LIST() DL_LIST_INSERT(H.root, A[i]) H.min = A[i] else: DL_LIST_INSERT_BEFORE(H.root, H.min, A[i]) if A[i].key < H.min.key: H.min = A[i] def FIB_HEAP_LINK(H, y, x): DL_LIST_DELETE(H.root, y) if x.child == None: x.child = DL_LIST() DL_LIST_INSERT(x.child, y) x.degree = x.degree + 1 y.parent = x y.mark = False def FIB_HEAP_DECREASE_KEY(H, x, k): if k > x.key: raise("new key is greater than current key") x.key = k y = x.parent if y != None and x.key < y.key: CUT(H, x, y) CASCADING_CUT(H, y) if x.key < H.min.key: H.min = x def CUT(H, x, y): DL_LIST_DELETE(y.child, x) y.degree = y.degree - 1 DL_LIST_INSERT_BEFORE(H.root, H.min, x) x.parent = None x.mark = False def CASCADING_CUT(H, y): z = y.parent if z != None: if y.mark == False: y.mark = True else: CUT(H, y, z) CASCADING_CUT(H, z) def FIB_HEAP_DELETE(H, x): FIB_HEAP_DECREASE_KEY(H, x, -float("inf")) FIB_HEAP_EXTRACT_MIN(H) if __name__ == "__main__": H = FIB_HEAP() node24 = NODE(24) FIB_HEAP_INSERT(H, node24) node17 = NODE(17) FIB_HEAP_INSERT(H, node17) node3 = NODE(3) FIB_HEAP_INSERT(H, node3) node23 = NODE(23) FIB_HEAP_INSERT(H, node23) node7 = NODE(7) FIB_HEAP_INSERT(H, node7) node39 = NODE(39) FIB_HEAP_INSERT(H, node39) node18 = NODE(18) FIB_HEAP_INSERT(H, node18) node52 = NODE(52) FIB_HEAP_INSERT(H, node52) node38 = NODE(38) FIB_HEAP_INSERT(H, node38) node41 = NODE(41) FIB_HEAP_INSERT(H, node41) node30 = NODE(30) FIB_HEAP_INSERT(H, node30) node35 = NODE(35) FIB_HEAP_INSERT(H, node35) node26 = NODE(26) FIB_HEAP_INSERT(H, node26) node46 = NODE(46) FIB_HEAP_INSERT(H, node46) FIB_HEAP_LINK(H, node39, node18) FIB_HEAP_LINK(H, node41, node38) FIB_HEAP_LINK(H, node35, node26) node39.mark = True FIB_HEAP_LINK(H, node38, node3) FIB_HEAP_LINK(H, node52, node3) FIB_HEAP_LINK(H, node18, node3) FIB_HEAP_LINK(H, node30, node17) FIB_HEAP_LINK(H, node46, node24) FIB_HEAP_LINK(H, node26, node24) node18.mark = True node26.mark = True print("init ********************") DL_LIST_PRINT(H.root) print("insert ******************") node21 = NODE(21) FIB_HEAP_INSERT(H, node21) DL_LIST_PRINT(H.root) print("extract******************") FIB_HEAP_EXTRACT_MIN(H) DL_LIST_PRINT(H.root) print("decrease*****************") FIB_HEAP_DECREASE_KEY(H, node46, 15) DL_LIST_PRINT(H.root) print("decrease-----------------") FIB_HEAP_DECREASE_KEY(H, node35, 5) DL_LIST_PRINT(H.root) print("delete*******************") FIB_HEAP_DELETE(H, node18) DL_LIST_PRINT(H.root)