堆排序的实现

#include <stdio.h>

void print_arry(const char *tips, const int *str, int length)
{
    int i;

    printf("%s\n\t", tips);

    for (i = 0; i < length; i++)
    {
        printf("%-8d", str[i]);
    }
    printf("\n");

    return;
}

void swap(int *array, int left, int right)
{
    int tmpval;
    if(left == right)
        return;

    if(array[left] == array[right])
        return;

    tmpval = array[left];
    array[left] = array[right];
    array[right] = tmpval;

    return;
}

int get_left_child_node(int node)
{
    return node * 2 + 1;
}

int get_right_child_node(int node)
{
    return node * 2 + 2;
}

int get_parent_node(int node)
{
    if(node == 0)
        return -1;
    return (node-1)/2;
}

void reorganized_max_heap(int *array, int node, int heap_size)
{
    int left, right, parent;
    int chg_node = node;

    if(node == -1)
        return;

    left = get_left_child_node(node);
    right = get_right_child_node(node);
    parent = get_parent_node(node);

    /**
     * if left child node bigger than heap size then return
     */
    if(left <= heap_size)
    {
        if(right > heap_size)
        {
            if(array[node] < array[left])
                chg_node = left;

            if(chg_node != node)
            {
                swap(array, node, chg_node);
            }

            reorganized_max_heap(array, parent, heap_size);
        }
        else
        {
            if((array[right] > array[left]) && (array[right] > array[node]))
                chg_node = right;

            if((array[left] > array[right]) && (array[left] > array[node]))
                chg_node = left;

            if(chg_node != node)
            {
                swap(array, node, chg_node);
            }
            reorganized_max_heap(array, parent, heap_size);
        }

    }
}

void build_max_heap(int *array, int heap_size)
{
    int tmpnode = 0;
    int mynode = 0;
    int node = (heap_size-1)/2;

    while(mynode <= node)
    {
        for(tmpnode = node; tmpnode >= mynode; tmpnode--)
        {
            reorganized_max_heap(array, tmpnode, heap_size);
        }
        mynode++;
        print_arry("build_max_heap",array, heap_size+1);
    }
}

void heap_sort(int *array, int heap_size)
{
    int node;

    build_max_heap(array, heap_size);
    swap(array, 0, heap_size);

    for(node = heap_size-1; node >= 0; node--)
    {
        print_arry("reorganized_max_heap before",array, heap_size+1);
        reorganized_max_heap(array, (node-1)/2, node);
        swap(array, 0, node);
    }
}

int main(void)
{
    int length;
    int array[] = {1, 10, 30, 40 ,2, 8, 50, 70, 6};

    length = sizeof(array)/sizeof(array[0]);

    print_arry("heap sort before print", array, length);
    heap_sort(array, length-1);
    print_arry("heap sort after print", array, length);

    return 0;
}