(Program C)add indicate the time complexity by counting the number of times Heap

Question

(Program C)add indicate the time complexity by counting the number of times Heapify is called

#include<stdio.h>

void printArray(int *a,int size);

void Heapify(int *a,int i,int j);

/*note: j is the last index for an array, not size!!!*/

int main()

{ int A[10]={16,11,9,10,5,6,8,1,2,4};

printf("Inital Array: ");

printArray(A,10); //output the initial array.

Heapify(A,0,9);

printf("Array after call Heapify(0,9): ");

printArray(A,10); //output the array.

}

void printArray(int *a,int size)

{int i;

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

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

printf(" ");

}

void Heapify(int *a,int i,int j)

{ if(2*i+1<=j) // to determine if a[i] is a leaf

   { int max;

   if(2*i+2<=j) //case1: a[i] has two children

{ if(a[2*i+1]>a[2*i+2]) // extract the index for the larger child to max.

   max=2*i+1;

else

   max=2*i+2;

}

   else

   max=2*i+1; //case2: a[i] has only one child

   if(a[i]<a[max]) //if the leaf is smaller than its child,to exchange their postion.

   { int temp=a[i];

   a[i]=a[max];

   a[max]=temp;

   Heapify(a,max,j);

   }

   }

}

Explanation / Answer

Note I didn't understood whether you want to add somthing to code that will find out the time complexity by counting number of times heapify is called

or

you want theoritical calculation

I am doing both for you

Code:

#include<stdio.h>
void printArray(int *a,int size);
void Heapify(int *a,int i,int j, int *cnt);
/*note: j is the last index for an array, not size!!!*/
int main()
{ int A[10]={16,11,9,10,5,6,8,1,2,4};
int cnt=0;
printf("Inital Array: ");
printArray(A,10); //output the initial array.
Heapify(A,0,9,&cnt);
printf("Array after call Heapify(0,9): ");
printArray(A,10); //output the array.
printf("Number of times hepify is called = %d ",cnt);
}

void printArray(int *a,int size)
{int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
printf(" ");
}

void Heapify(int *a,int i,int j, int *cnt)
{
(*cnt)+=1;
if(2*i+1<=j) // to determine if a[i] is a leaf
{
int max;
if(2*i+2<=j) //case1: a[i] has two children
{
if(a[2*i+1]>a[2*i+2]) // extract the index for the larger child to max.
max=2*i+1;
else
max=2*i+2;
}
else
max=2*i+1; //case2: a[i] has only one child


if(a[i]<a[max]) //if the leaf is smaller than its child,to exchange their postion.
{
int temp=a[i];
a[i]=a[max];
a[max]=temp;
Heapify(a,max,j,cnt);
}
}
}

Theoritical calculation:

each time you are calling void Heapify(int *a,int i,int j), it is checking whether the element at index i is less than its children( elements at index 2*i+1, 2*i+2) or not, if it is greater , it is done

else

it is swapping this element with the maximum element out of children, and calling hepify function recursively with i value as it's child index having maximum value

since

each time when it is calling function with i value as either 2*i+1 or 2*i+2 (i.e i value is getting doubled each time)

since i value is getting doubled each time worst case time complexity = O(n) or O(j)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.