Heap sort (힙정렬)

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

void swap(int* arr1, int* arr2)
{
        int temp = *arr1;
        *arr1 = *arr2;
        *arr2 = temp;
}
void heapify(int* arr, int here, int size)
{
        int left = here*2+1;
        int right = here*2+2;
        int max = here;

        if ( arr[left] > arr[max] && left < size ) // 왼쪽 자식노드와 현재 노드와 비교해서 큰걸 max에
                max = left;
        if ( arr[right] > arr[max] && right < size ) // 오른쪽 자식노드와 위의 if문에서 걸러진 더 큰노드와 비교해서 더 큰걸 max에 ㅑ
                max = right;

        if ( max != here ) // 부모와 자식노드가 바뀌었단 소리 -> here보다 더 큰 노드가 max가 되므로 max의 자식노드도 다시 검사해야 함, buildHeap할땐 필요 없음
        {
                swap(&arr[here], &arr[max]);
                heapify(arr, max, size);
        }
}
void buildHeap(int *arr, int size)
{
        int i;
        for (i = (size/2)-1; i>=0; i--) //자식이 있는 노드만 돌면서 자식노드와 크기 비교
        {
                heapify(arr, i, size);
        }
}
void heapSort(int* arr, int size)
{
        int treeSize;
        buildHeap(arr, size); // 일단 최대값이 root에 있는 상태

        for ( treeSize = size-1; treeSize >= 0; treeSize-- )
        {
                swap(&arr[0], &arr[treeSize]); // arr[0]==root에 있는 가장 큰 수를 배열의 맨 마지막으로 보내고
                heapify(arr, 0, treeSize);  // 마지막 배열을 제외한 나머지 배열에 대해서 root부터 돌면서 큰순서대로 정렬
        }
}
int main()
{
        int size;
        int* arr;

        scanf("%d", &size);

        arr = (int *)malloc(sizeof(int)*size);

        for (int i=0; i<size; i++)
                scanf("%d", &arr[i]);

        heapSort(arr, size);
        for (int i=0; i<size; i++)
        {
                printf("%d ", arr[i]);
        }

        free(arr);
}