首页 > 试题广场 >

从左式堆中一个已知位置删除节点的一种方法是使用懒惰策略。要删

[问答题]
从左式堆中一个已知位置删除节点的一种方法是使用懒惰策略。要删除一个节点,只要将其标记为已被删除即可。当执行一个FindMin或DeleteMin时,若标记根节点被删除则存在一个潜在的问题,因为此时节点必须被实际删除且需要找到实际的最小元,这可能涉及到删除其它一些已做标记的节点。在该方法中,Delete花费一个单位,但一次DeleteMin或FindMin的开销却依赖于被做删除标记的节点的个数。设在一次DeleteMin或FindMin后做标记的节点比操作前少了k个。
a. 说明如何以O(klogN)时间执行DeleteMin
b. 提出一种实现方法,通过分析证明执行DeleteMin的时间为O(klog(2N/k)).

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