Consider the following "Max Heapify" algorithm. Array has atleast n and 1<=i<=n. After applying the Max-heapify rooted at A[i], the result will be subtree of A[1,....n] rooted at A[i] is max heap. [Assume that except root A[i], all its children satisfied heap property]
Max-heapify(int A[], int n, int i)
{
int p,m;
p=i;
while(X)
{
if(Y&&Z)
m=2p+1;
else m=2p;
if(A[p]<A[m])
{
Swap(A[p],A[m]);
p=m;
}
else
return;;
}
}
Find missing statements at X, Y and Z respectively to apply the heapify for subtree rooted at A[i].
a) p<=n, (2p+1)>=n, A[2p+1]>A[2p]
b) 2p<=n, (2p+1)<=n, A[2p+1]>A[2p]
c) 2p<=n, (2p+1)>=n, A[2p+1]<A[2p]
d) p<=n, (2p+1)<=n, A[2p+1]<A[2p]
