recategorized by
1,025 views
2 votes
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.
GO2019-FLT1-45 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::

  1. $9 \: 4 \: 1 \: 8 \: 6$
  2. $6 \: 8 \: 1 \: 9 \: 4$
  3. $9 \: 6 \: 1 \: 8 \: 4$
  4. $6 \: 9 \: 1 \: 8 \: 4$
recategorized by

2 Answers

Best answer
0 votes
0 votes

$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 :/

selected by
0 votes
0 votes
for a subtree if it satisfies min heap then go to min element and swap with it else if it satisfies max heap then  go to max element and swap with it.  hence C)
Answer:

Related questions

8 votes
8 votes
2 answers
2
Ruturaj Mohanty asked Dec 27, 2018
1,269 views
For a given $m$-ary tree, the relationship between leaf nodes and internal nodes is represented by the graph given below. What is the value of $'m'$? Take necessary appro...