算法导论 CLRS 19.2-10 解答

it2022-05-09  41

1.  Extract-Min: 最小节点在Bmax中,删除需要O(lgN)

     Decrease-Key: 将Bmax中的一个叶节点降低为比Bmax的根还小,冒泡需要O(lgN)

     Delete: 同Extract-Min即可

     Union: 合并的H'有lgN个二项树,总是要O(lgN)

 

2. Insert: 当n为偶数的时候,插入总是只要O(1),不存在为O(lgN)的情况

    Minimum: 当n为2的整数次幂时,min操作只要O(1),不存在为O(lgN)的情况

转载于:https://www.cnblogs.com/ellusak/archive/2012/07/26/2609710.html


最新回复(0)