首页 > 试题广场 >

(删除操作的另一种是实现)Pisano教授提出了下面的FIB

[问答题]
(删除操作的另一种是实现)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时也是如此。

这道题你会答吗?花几分钟告诉大家答案吧!