Professor Pisano has proposed the following variant of the FIB-HEAP-DELETE procedure, claiming that it runs faster when the node being deleted is not the node pointed to by H.min.

PISANO-DELETE(H, x)

a. The professor?s claim that this procedure runs faster is based partly on the assumption that line 7 can be performed in O(1) actual time. What is wrong with this assumption?

b. Give a good upper bound on the actual time of PISANO-DELETE when x is not H.min. Your bound should be in terms of x.degree and the number c of calls to the CASCADING-CUT procedure.

c. Suppose that we call PISANO-DELETE(H, x), and let H? be the Fibonacci heap that results. Assuming that node x is not a root, bound the potential of H? in terms of x:degree, c, t(H), and m(H).

d. Conclude that the amortized time for PISANO-DELETE is asymptotically no better than for FIB-HEAP-DELETE, even when x ? H.min.

Transcribed Image Text:

1 if x == H.min FIB-HEAP-EXTRACT-MIN (H) 3 else y = x.p if y + NIL CUT(H,x, y) CASCADING-CUT(H, y) add x's child list to the root list of H 4 5 7 8 remove x from the root list of H