Q) 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 min[H].
PISANO-DELETE(H, x) 1 if x = min[H] 2 then FIB-HEAP-EXTRACT-MIN(H) 3 else y p[x] 4 if y NIL 5 then CUT(H,x,y) 6 CASCADING-CUT(H,y) 7 add x's child list to the root list of H 8 remove x from the root list of 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 of PISANO-DELETE when x min[H]. Your bound should be in terms of degree[x] and the number c of calls to the CASCADING-CUT procedure. c. Let H' be the Fibonacci heap that results from an execution of PISANO-DELETE(H, x). 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 for PISANO-DELETE is asymptotically no better than for FIB-HEAP-DELETE, even when x min[H]. On Dec 7, 9:51 pm, "James Fang" <[EMAIL PROTECTED]> wrote: > Could u post the problem ? > > -----邮件原件----- > 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表 > doubt > 发送时间: 2007年12月8日 11:40 > 收件人: Algorithm Geeks > 主题: [algogeeks] Solution for problem 20-1 > > Does anybody have solution for problem 20-1 in cormen --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
