C Program to construct Max Heap and Sort an Array based on Heap Sort Algorithm

".C" file is available in downloadable format at :

https://drive.google.com/open?id=0ByF0OId1bLx6M2R3YV9fOFd1QnM

(Open the link and click on the download arrow on the top right to download the file.)

Given below is the code for "C Program to construct Max Heap and Sort an Array based on Heap Sort Algorithm" :

-----------------------------------------------------------------------------------

#include <stdio.h>

 

void main()

{

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

 

printf("\nEnter no of elements :");

scanf("%d", &no);

printf("\nEnter the nos : ");

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

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

for (i = 1; i < no; 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("Here's the max Heap : ");

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

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

for (j = no - 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("\nThe sorted array is : ");

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

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

printf("\nComplexity :  Best case = Avg case = Worst case = O(n logn) \n");

}