/*
 * 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");
}
/*
*OUTPUT:
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)

/* 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)

/* 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)
*/