This C Program sorts an array based on heap sort algorithm.

Here is source code of the C Program to sort an array based on heap sort algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C Program to sort an array based on heap sort algorithm(MAX heap)`

`*/`

`#include <stdio.h>`

void main()

`{`

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

printf("\n Enter no of elements :");

scanf("%d", &no);

printf("\n Enter 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("Heap array : ");

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("\n The sorted array is : ");

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

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

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

`}`

$ cc heap.c $ a.out Average case Enter no of elements :7 Enter the nos : 6 5 3 1 8 7 2 Heap array : 8 6 7 1 5 3 2 The sorted array is : 1 2 3 5 6 7 8 Complexity : Best case = Avg case = Worst case = O(n logn) $ a.out /* Best case Enter no of elements :7 Enter the nos : 12 10 8 9 7 4 2 Heap array : 12 10 8 9 7 4 2 The sorted array is : 2 4 7 8 9 10 12 Complexity : Best case = Avg case = Worst case = O(n logn) $ a.out /* Worst case Enter no of elements :7 Enter the nos : 5 7 12 6 9 10 14 Heap array : 14 9 12 5 6 7 10 The sorted array is : 5 6 7 9 10 12 14 Complexity : Best case = Avg case = Worst case = O(n logn) */

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.