6.3-2 Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from A{length/2} to 1 rather than increase from 1 to A[length/2]? This is because it will the precondition MAX-HEAPIFY condition is met before calling it.i.e if we increase from 1 to A[length/2] the precondition will fail and the loop invariant will not hold. If we decrease from A{length/2} to 1 we will max- heaps in both left and right subtrees.
Friday, January 11, 2013
6.3-2
6.3-2 Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from A{length/2} to 1 rather than increase from 1 to A[length/2]? This is because it will the precondition MAX-HEAPIFY condition is met before calling it.i.e if we increase from 1 to A[length/2] the precondition will fail and the loop invariant will not hold. If we decrease from A{length/2} to 1 we will max- heaps in both left and right subtrees.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment