Dark Mode

759 views

2 votes

Consider the following modified Heapify and Build_heap procedure.

void Heapify(int* A, int i, int n) {

int left=2*i+1;

int right=2*i+2;

int mid=i;

if (left<=n && right <=n) {

if ((A[left] > A[right] && A[left]< A[i]) || A[left]<A[right] && A[left] >A[i])

mid=left;

else if((A[left<A[right] && A[right]<A[i]) || A[left] >A[right] && A[right]>A[i])

mid=right;

else mid=i;

}

if (mid!=i) {

swap(A[i], A[mid]);

Heapify(A, mid, n);

}

}

void Build_heap (int *A, int n) {

int i=0;

for (i=n; i>=0;i--) {

Heapify(A, i, n);

}

}

Now consider the following binary tree.

This binary tree is stored in an array $A$ starting from index $0$ as the root node of the binary tree. The left and right child are stored at location $2i+1$ and $2i+2$ respectively, where $i$ is the position of the parent.

If the above given Build_heap() procedure is applied on this binary tree, then the correct order of elements stored in the array $A$ is::

- $9 \: 4 \: 1 \: 8 \: 6$
- $6 \: 8 \: 1 \: 9 \: 4$
- $9 \: 6 \: 1 \: 8 \: 4$
- $6 \: 9 \: 1 \: 8 \: 4$

0

0 votes

Best answer

$n=5;$

First iteration: i=5; // as i=n;

So,

$left=2*5+1=11$

$right=2*5+2=12$

$mid=5,$

But the condition $\text{if (left<=n && right <=n)}$ FAILS as left and right are not less than equal to n which is 5.

This way, this condition will fail for each leaf node, and will work only when $i=1 or i=0$

**Case 1:** when $i=1$ then

$left=3$

$right=4$

$mid=1$

$A[1]=1$

$A[3]=8$

$A[4]=6$

$if ((A[3]>A[4] $&& $A[3]<A[1])$ || $(A[3]<A[4]$ && $A[3]>A[1]))$

condition is false as $A[3]!<A[1]$ and $A[3]!<A[4]$

So control goes to else part.

$if((A[3]<A[4]$&&$A[4]<A[1])$ || $(A[3]>A[4]$&&$A[4]>A[1]))$

And, second part of the if clause is true as $A[3]>A[4]$ and $A[4]>A[1]$

Hence, $mid=right;$ $Mid=4$

So 4 and 6 will be swapped, and following will be resulted tree:

**Case 2:** i=0

$left=1$

$right=2$

$mid=0$

$A[0]=9$

$A[1]=6$

$A[2]=1$

$if ((A[1]>A[2]$&&$A[1]<A[0])$ || $(A[1]<A[2]$&&$A[1]>A[0])$

if results true as $A[1]>A[2]$ and $A[1]<A[0]$, so mid=left;

Now, $swap(A[i],A[mid])$, Swap A[0] and A[1] so the following will be the resulted tree:

Now, $Heapify(A,mid,n)$ is called. SO the call will be $Heapify(A,1,5)$

$left=3$

$right=4$

$mid=1$

$A[1]=9$

$A[3]=8$

$A[4]=4$

$if ((A[3]>A[4]$ &&$ A[3]<A[1])$ || $(A[3]<A[4]$ && $A[3]>A[1]))$

This condition is true as $A[3]>A[4]$ and $A[3]<A[1]$, Hence $Mid=left$.

$Swap(A[i],A[mid])$ which is $Swap(A[1],A[3])$;

And following is the resulted tree:

So, output will be $6, 8, 1, 9, 4$, **which is option (B).**

**PS:** the given method is incorrect as it is making the given Binary Tree into neither Max - Heap nor Min-Heap :/

yes its not a max heap I run the entire code to today don't have any other technique ....thanks Ruturaj Mohanty its a great concept clearing question

0