Shubh - 2 months ago 7x

C Question

I am trying to build max heap from a random array so that i can get largest number in the root.

Also plese suggest me, how to get the size of the heap in the heapify() function.

`#include<stdio.h>`

#include<math.h>

int i;

void heapify(int a[],int i) //n=node at which heapify needs to apply

{

int size=8;

int max=i,l=2i,r=2i+1;

if(a[l]>a[max] && l<=size)

max=l;

if(a[r]>a[max] && r<=size)

max=r;

if(max==i) return;

else

a[max]^=a[i]^=a[max]^=a[i];

heapify(a,max);

}

//Using this function to call recursively heapify to maintain heap data structure

void build_heap(int arr[],int n) //n : size of array

{

for(i=floor(n/2);i>0;i--) // n/2 because after that every node is a leaf node and they follow heap property by default

{

heapify(arr,i);

}

}

int main()

{

int arr[] = {2,5,4,8,9,10,3,1};

build_heap(arr,8);

for(i=0;i<8;i++)

{

printf("%d ",arr[i]);

}

return 0;

}

Answer

Your code seems to be fine except for a few changes:

- Change
`2i`

and`2i+1`

to be`2*i`

and`2*i+1`

otherwise you'll get a compilation error. Actually it should really be`l = 2*i+1`

and`r = 2*i+2`

because C arrays are`0-indexed`

. You are assuming`1-based`

indexing in your code. - In
`build_heap()`

, run the loop from`[floor(n/2), 0]`

(you excluded`0`

'th element probably because of the reason stated in the above point).

You can pass the size of the heap as an argument to the `heapify()`

function or declare it as a global variable (though it is advised to avoid global variables).

Source (Stackoverflow)

Comments