Code:
#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]
{
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");
}
Output:
$ 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)
More C Programs:
