16 6 MAX-HEAPIFY(A,i) 10 0 1 I=LEFT(i) 2 r=RIGHT(i) 3 if1 A.heap-size and A[l]>Ali] 4 largest =I 5 else largest =i (b】 6 ifr A.heap-size and A[r]>A[largest] 7 largest =r 8 if largest≠i 16 9 exchange A[i]with A[largest] 10 MAX-HEAPIFY (A,largest) MAX-Heapify操作的pre/post--condition是什么？ Pre-condition:i的子女均已是某个大堆的根节点！ Post-condition:以i为根，构成一个大堆！
MAX-Heapify操作的pre/post-condition是什么？ Pre-condition: i的子女均已是某个大堆的根节点！ Post-condition: 以i为根，构成一个大堆！
Worst-case Analysis for Max-Heapify ·过程Max-Heapify中不包含循环，所以，如果不递归，其 代价是O(1)。 口如果考虑比较运算的次数，每“下沉”一层，执行2次比较。 ·递归：T(m)≤T(2n/3)+Θ(1) 问题5： 为什么2n/3? The solution to this recurrence,by case 2 of the master theorem (Theorem 4.1). is T(n)=0(lg n).Altematively,we can characterize the running time of MAX- HEAPIFY on a node of height h as ()
Worst-case Analysis for Max-Heapify ◼ 过程Max-Heapify中不包含循环，所以，如果不递归，其 代价是O(1)。 ❑ 如果考虑比较运算的次数，每“下沉”一层，执行2次比较。 ◼ 递归：
造“堆”：自底向上 413216 9 101487 ·分界线 问题6：这5个子树 LA.length/2] 己经是“堆”了？ 其实后T27个子树 10 己经是“堆”了 其实算法循环从 A.length开始又何妨？
问题6：这5个子树 已经是“堆”了？ 造“堆”：自底向上 分界线 其实后┌n/2┒个子树 已经是“堆”了 其实算法循环从 A.length开始又何妨？