sort: heapSort

#include
#include

int g_heap_size;

void set_heap_size(int heapSize)
{
    g_heap_size = heapSize;
}

int get_heap_size()
{
    return g_heap_size;
}

#define LCHILD(i) (2 * (i))
#define RCHILD(i) (2 * (i) + 1)

void max_heapify(int* A, int i)
{
    int lchild, rchild, largerInd = i;
    int heapSize = get_heap_size();
    
    lchild = LCHILD(i);
    rchild = RCHILD(i);

    if (lchild <= heapSize && A[lchild] > A[i])
    {
        largerInd = lchild;
    }

    if (rchild <= heapSize && A[rchild] > A[largerInd])
    {
        largerInd = rchild;
    }

    if (largerInd != i)
    {
        int tmp = A[i];
        A[i] = A[largerInd];
        A[largerInd] = tmp;
        max_heapify(A, largerInd);
    }
}

void build_max_heap(int *A, int arrLen)
{
    set_heap_size(arrLen);
    int heapSize = get_heap_size();

    for (int i = heapSize / 2; i >= 1; i--)
    {
        max_heapify(A, i);
    }
}

void heap_sort(int* A, int arrLen)
{
    build_max_heap(A, arrLen);
    int heapSize = get_heap_size();

    while (heapSize > 1)
    {
        int tmp = A[1];
        A[1] = A[heapSize];
        A[heapSize] = tmp;

        heapSize--;
        set_heap_size(heapSize);

        max_heapify(A, 1);
    }
}

void test_heap_sort()
{
    int A[6] = { 0,5,4,3,2,1 };

    heap_sort(A, 5);

    for (int i = 1; i < 6; i++)
    {
        printf("%d t",A[i]);
    }
    printf("n");
}

int main()
{
    test_heap_sort();
    return 0;
}