首页 > 试题广场 >

(更多的斐波拉契堆的操作)想要扩展斐波拉契堆H支持两个新操作

[问答题]
(更多的斐波拉契堆的操作)想要扩展斐波拉契堆H支持两个新操作,要求不改变斐波拉契堆的其他操作的摊还时间。
a.操作FIB-HEAP-CHANGE-KEY(H,x,k)将节点x中关键字的值改为k,给出FIB-HEAP-CHANGE-KEY的一个有效实现,并分析当k大于,小于或等于x.key时,各情况下的摊还运行时间。
b.给出FIB-HEAP-PRUNE(H,r)的一个有效实现,该操作从H中删除q=min(r,H.n)个节点,可以选择任意q个节点来删除。试分析你的实现的摊还运行时间。(提示:可能需要修改数据结构以及势函数。)

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