heap

/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

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

int size;

int main()
{
    int A[100] = {};
    
    printf("size : ");
    scanf("%d", &size);
    for(int i = 0; i < size; i++){
        scanf("%d", &A[i]);
    }
    Heapsort(A, size);
    print_ar(A);

    return 0;
}

int print_ar(int *A){
    for(int i = 0; i < size; i++){
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

int Heapsort(int A[], int n){
    int tmp;
    Build_heap(A, n);
    for(int i = n; i > 0; i--){

        
        tmp = A[0];
        A[0] = A[i-1];
        A[i-1] = tmp;
        
        Heapify(A,0,i-1);

    }
    
    return 0;
}

int Build_heap(int A[], int n){

    for(int i = n/2-1; i >= 0; i--){
        Heapify(A, i, n);    //i가 n부터 시작해도 될까? 시간을 절약하기 위해서 n/2-1부터 시작인걸까?

    }
    
    return 0;
}

int Heapify(int A[], int i, int n){
    int j = i;
    int max;
    int tmp;
    
    while(1){

        if(2*j + 1 < n && A[2*j + 1] > A[j]){  //왼쪽 자식노드가 n보다 작고 부모보다 크다면
            max = 2*j+1;  
        } else{
            max = j;
        }

        if(2*j+2 < n && A[2*j + 2] > A[max]){  //오른쪽 자식노드가 n보다 작고 부모보다 크다면
            max = 2*j + 2;
        } 

        if(max != j){    //최댓값이 j가 아니라면 교환
            tmp = A[j];
            A[j] = A[max];
            A[max] = tmp;

            
        } else  break;
        Heapify(A, max, n);
    }

    return 0;
}