山东建筑大学计算机学院算法分析算法复习题（Yuconan翻译）上课讲义 

精品文档

十六

Heapify(A, i) { l = Left(i); r = Right(i); if (l <= heap_size(A) && A[l] > A[i]) largest = l; else largest = i; if (r <= heap_size(A) && A[r] > A[largest]) largest = r; if (largest != i) Swap(A, i, largest); Heapify(A, largest); }

Fixing up relationships between i, l, and r takes ?(1) time，If the heap at i has n elements, the subtrees at l or r can have 2n/3 elements. So time taken by Heapify() is given by T(n) ? T(2n/3) + ?(1) ,by recursive tree, the solution is T(n) = O(lg n) .算法描述4分 列递归方程3分，求解3分

收集于网络，如有侵权请联系管理员删除