// To implement heap sort

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

void display(int a[], int n){
    int i;
    printf("\n Elements in array: ");
    for( i=0; i<n; i++)
        printf(" %d ", a[i]);
}

void heapify( int a[], int n, int index){
    // left & right child
    int left = 2*index, right = 2*index+1;
    int max = index, tmp; // maximum
    
    if( left<n && a[left]>a[max] )
        max = left;
    if( right<n && a[right]>a[max] )
        max = right;

    if( max!=index ){
        // swap max and parent
        tmp=a[max], a[max]=a[index], a[index]=tmp;
        heapify( a, n, max);
    }
}


void buildheap( int a[], int n){
    int i;
    
    for( i=n/2; i>=0; i--)
        heapify( a, n, i );
}

void sort( int a[], int n){
    int i, tmp;
    
    buildheap( a, n);
    
    for( i=n-1; i>0; i--){
        // swap root with last
        tmp=a[i], a[i]=a[0], a[0]=tmp;
        heapify( a, i, 0);
    }
}

int main(){
    int a[20];
    int n, i;
    
    printf("\n Enter total number of elements in array (max. %d): ", MAX);
    scanf("%d", &n);
    
    if( n < 0)
        printf("UNDERFLOW \n");
    else if( n > MAX)
        printf("OVERFLOW \n");
    else{
        // input elements one by one
        printf("\n Enter item(s) one by one\n");
        for( i=0; i<n; i++){
            printf(" Enter item no %d : ",i);
            scanf("%d", &a[i]);
        }
        
        printf("\n Before Sorting");
        display(a,n);
        sort( a, n);
        printf("\n After Sorting");
        display(a,n);
        printf("\n ");
    }
        
    system("pause");
    return 0;
}