# Cormen Edition 3 Exercise 6.3 Question 2 (Page No. 159)

21 views

Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfloor$?

## Related questions

1
35 views
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i) Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle$
HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error new key is smaller than current key 3 A[i] = key 4 while i > 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i)] 6 i=parent(i) MAX-HEAP-INSERT(A,key) 1 A.heapsize = A.heapsize + 1 2 A[A.heapsize] ... -KEY(A,A.heapsize,key) Illustrate the operation of MAX-HEAP-INSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a max-heap containing the $i$ smallest elements of $A[1..n]$, and the subarray $A[i+1..n]$ contains the $n- i$ largest elements of $A[1..n]$, sorted.