Professor Pisano has proposed the following variant of theFib-Heap-Delete procedure, claiming that it runs faster when the node being deleted is not the node pointed to by min[H].
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 ofpIsano-delete when x is not min[H]. Your bound should be in terms of degree[x] and the number c of calls to theCascading-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 degree [x], c, t(H), and m(H).
d. Conclude that the amortized time forPisano-Delete is asymptotically no better than forFib-Heap-Delete, even when\x ≠ min[H].