6.2-1参照图6.2的方法，说明MAX-HEAPIFY(A,3)在数组A={27,17,3,16,13,10,1,5,7,12,4,8,9,0}
上的操作过程。
操作过程参照书中图6.2，非常类似。
6.2-2参考过程MAX-HEAPIFY，写出能够维护相应最小堆的MIN-HEAPIFY(A,i)的伪代码，并比较
MIN-HEAPIFY与MAX-HEAPIFY的运行时间。
把原书伪代码A[l]>A[i]与A[r]>A[largest]都改成小于就OK了。
6.2-3当元素A[i]比其孩子的值都大时，调用MAX-HEAPIFY(A,i)会有什么结果？
调用后，原最大堆不会有任何元素位置的改变。
6.2-4当i>A.heap-size/2时，调用MAX-HEAPIFY(A,i)会有什么结果？
那么i都是叶子结点，所以原最大堆也不会改变。
6.2-5MAX-HEAPIFY的代码效率较高，但第10行中的递归调用可能例外，它可能使某些编译器产生
低效的代码。请用循环控制结构取代递归，重写MAX-HEAPIFY代码。
- MAX-HEAPIFY(A,i)
- while (i<=A.heap-size/2)//由于6.2-4知道，i>A.heap-size/2以后，最大堆不会有任何改变。
- { //这样也可以减少循环次数。
- l=LEFT(i)
- r=RIGHT(i)
- if l<=A.heap-size and A[l]>A[i]
- largest=l
- else largest=i
- if r<=A.heap-size and A[r]>A[largest]
- largest=r
- if largest!=i
- exchange A[i]<->A[largest]
- i=largest//把largest赋值给i，然后继续进行MAX-HEAPIFY(A,i)循环。
- }
6.2-6 证明：对一个大小为n的堆，MAX-HEAPIFY的最坏情况运行时间为Ω(lgn).
由书中知：T(n)<=T(2n/3)+Θ(1) 最坏情况发生在树最底层半满时候，所以
T(n)最坏=T(2n/3)+Θ(1) 根据主定理的第二种情况n^(log(3/2,1))=Θ(1)
T(n)最坏=Θ(lgn) 而Θ(lgn)包含了Ω(lgn).
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
