#include <stdlib.h>
#include <stdio.h>


int parent(int i);
int left(int i);
int right(int i);
void przywroc(int*K, int heap_size, int i);
void buduj(int*K, int heap_size);
int maks(int *K, int n);
int mini(int *K, int n);
void sort_kopcowanie(int*K, int heap_size);
void sort_zliczanie(int*K,int n);

int main(){
    int*K = NULL;
    int n=0;
    int x;
    int i;
    char z;

    srand (time(NULL));

    while(1){
        printf("\n Co chcesz:");
        printf("\n b - buduj");
        printf("\n d - wstaw");
        printf("\n w - wyswietl");
        printf("\n k - sort kopcowanie");
        printf("\n z - sort zlicznanie");
        printf("\n q - zakoncz \n ");

        fflush(stdin);
        z = getchar();
        switch(z){
        case 'b' :  buduj(K,n);
                    break;

        case 'd' :  /*fflush(stdin);
                    scanf("%d",&x);
                    K = (int*)realloc(K,(n+1)*sizeof(int));
                    *(K+n) = x;
                    n++;
                    break;
                    */
                    n = 10;
                    K = (int*)realloc(K,(n)*sizeof(int));
                    for(i=0; i<n; i++)
                        *(K+i) = rand()%100;

        case 'w' :  for(i=0; i<n; i++)
                        printf("%d, ",*(K+i));
                    break;
        case 'k' :  sort_kopcowanie(K,n);

                    for(i=0; i<n; i++)
                        printf("%d, ",*(K+i));

                    break;
        case 'z' :  sort_zliczanie(K,n);

                    for(i=0; i<n; i++)
                        printf("%d, ",*(K+i));

                    break;

        case 'q' : return 0;
        }
    }
}

int parent(int i){
    return (i-1)/2;
}

int left(int i){
    return 2*i+1;
}

int right(int i){
    return 2*i+2;
}

void przywroc(int*K, int heap_size, int i){
    int temp;
    int r = right(i);
    int l = left(i);
    int max;

    if(l<heap_size && *(K+l)>*(K+i))
        max = l;
    else
        max = i;
    if(r<heap_size && *(K+r)>*(K+max))
        max = r;

    if(max!=i){
        temp = *(K+i);
        *(K+i) = *(K+max);
        *(K+max) = temp;
        przywroc(K,heap_size,max);
    }
}

void buduj(int*K, int heap_size){
    int k;

    for(k=heap_size/2-1;k>=0;k--)
        przywroc(K,heap_size,k);
}

void sort_kopcowanie(int*K, int heap_size){
    int i,temp;

    for(i=heap_size-1;i>0;i--){
        buduj(K,heap_size);
        temp = *K;
        *K = *(K+i);
        *(K+i) = temp;
        heap_size = heap_size - 1;
    }
}

int maks(int *K,int n){
    int max,i;

    max = *K;
    for(i=0;i<n;i++){
        if(max<*(K+i))
            max = *(K+i);
    }

    return max;
}

int mini(int *K,int n){
    int mini,i;

    mini = *K;
    for(i=0;i<n;i++){
        if(mini>*(K+i))
            mini = *(K+i);
    }

    return mini;
}

void sort_zliczanie(int*K,int n){
    int k1,k2,k,i;
    int*B = NULL,*C = NULL;

    k1 = maks(K,n);
    k2 = mini(K,n);
    k = k1 - k2;

    C = (int*)realloc(C,(k+1)*sizeof(int));
    for(i=0;i<k+1;i++)
        *(C+i)=0;
    for(i=0;i<n;i++)
        *(C+*(K+i)-k2) = *(C+*(K+i)-k2) + 1;
    for(i=1;i<k+1;i++)
        *(C+i)=*(C+i) + *(C+(i-1));

    B = (int*)realloc(B,n*sizeof(int));

    for(i=0;i<n;i++){
        *(B+*(C+*(K+i)-k2)-1) = *(K+i);
        *(C+*(K+i)-k2) = *(C+*(K+i)-k2) - 1;
    }
    for(i=0;i<n;i++)
        *(K+i) = *(B+i);
        free(B);
        free(C);
}