Alternative implementation of deletion Professor Pisano

Chapter 19, Problem 19-1

(choose chapter or problem)

Alternative implementation of deletion 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/ 1 if x = = H:min 2 FIB-HEAP-EXTRACT-MIN.H / 3 else y D x:p 4 if y NIL 5 CUT.H; x; y/ 6 CASCADING-CUT.H; y/ 7 add xs child list to the root list of H 8 remove x from the root list of H a. The professors 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 H0 be the Fibonacci heap that results. Assuming that node x is not a root, bound the potential of H0 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.