Given the following array A1 10 15 3 29 1 30 5 19 7 24 11

Given the following array A[1 . . . 10]: 15 3 29 1 30 5 19 7 24 11

(a) Show the array after it has been “heapified”.

(b) After the maximum value has been moved to A[10] and the heap (in A[1 . . . 9]) has been “re-heapified”.

(c) After the next largest element has been moved to A[9] and the heap (in A[1 . . . 8])has been “re-heapified”.

(a) A[1 to 10] = 15 3 29 1 30 5 19 7 24 11 Array after heapified = 30,29,19,24,11,5,15,1,7,3

(b) A[1 to 9] = 3 29 19 24 11 5 15 1 7 | 30

Array after re-heapified = 29,24,19,7,11,5,15,1,3 | 30

(c) A[1 to 8] = 3 24 19 7 11 5 15 1 | 29 30

Array after re-heapified = 24,11,19,3,7,5,15,1 | 29,30

Solution

#include <stdio.h>

int main()

{

int heap[10],n,i,j,c,root,temp;

printf(\"Enter no. of elements\");

scanf(\"%d\",&n);

printf(\"Enter array elements to be sorted\");

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

scanf(\"%d\",&heap[i]);

for(i=1;i<n;i++)

{

c=i;

do

{

root=(c-1)/2;

if(heap[root]<heap[c]) // to create MAX heap array

{

temp=heap[root];

heap[root]=heap[c];

heap[c]=temp;

}

c=root;

}while(c!=0);

}

printf(\"Heap Array : \");

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

printf(\"%d\\t\",heap[i]);

for(j=n-1;j>=0;j++)

{

temp=heap[0];

heap[0]=heap[j]; // swap max element with rightmost leaf element

heap[j]=temp;

root=0;

do{

c=2*root+1; //left node of root element

if(heap[c]<heap[c+1]&&c<j-1)

c++;

if(heap[root]<heap[c]&&c<j)// again rearrange to MAX heap array

{

temp=heap[root];

heap[root]=heap[c];

heap[c]=temp;

}

root=c;

}while(c<j);

}

printf(\"Sorted Elements are : \ \");

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

printf(\"%d\\t\",heap[i]);

}