in Algorithms recategorized by
759 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$
in Algorithms recategorized by
759 views

3 Comments

Min heap?
0
0
No... If you have properly understood internal implementation and how heaps work you can easily solve it.
0
0
Please help me ...I am thinking this way.. that in build heap i= 5 ,i>0 it will go to heapify function but because left and right will be greater than >n so it will fail untill i=1 then left will be 3 and right is 4
0
0

2 Answers

0 votes
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 :/

selected by

4 Comments

It is not a max heap.... So no point of mentioning it!!!
0
0
it's fine now? neither max-heap nor min-heap :/
0
0
Yes...do why have mentioned it as incorrect?...It's a modified heap as quoted from start.
0
0

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

0
0
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