(删除操作的另一种是实现)Pisano教授提出了下面的FIB-HEAP-DELETE过程的一个变种,声称如果删除的节点不是由H.min指向的节点,那么程序运行的更快。
PISANO-DELETE(H,x) 1 if x==H.min 2 FIB-EXTRACT-MIN(H) 3 else y=x.p 4 if yNIL 5 CUT(H,x,y) 6 CASCADIING-CUT(H,y) 7 add x's child list to the root list of H 8 remove x from the root list fo H
a.该教授声称是基于第7行可以在O(1)时间内完成这一假设,它的程序可以运行的更快,该假设有什么问题吗?
b.当x不是由H.min指向时,给出PISANO-DELETE实际时间的一个好上界。你给出的上界应该以x,degree和调用CASCADING-CUT的次数c这两个参数来表示。
c.假定调用PISANO-DELETE(H,x),并设H'是调用后得到的斐波拉契堆。假定节点x不是一个根,用x.degree,c,t(H)和m(H)来表示H'势的界。
d.证明:PISANO-DELETE的摊还时间渐近的不好于FIB-HEAP-DELETE的摊还时间,即使xH.min时也是如此。