heap sort--堆排序

#include <stdio.h>

#define LEFT(i) i*2
#define RIGHT(i) i*2+1

void max_heapify(int array[], int i, int heap_size)
{
    int l, r, largest, tmp;

    l = LEFT(i); r = RIGHT(i);
    if(l <= heap_size && array[l] > array[i] && array[l] > array[r])
        largest = l;
    else
        largest = i;

    if(r <= heap_size && array[r] > array[i] && array[r] > array[l])
        largest = r;

    if(largest != i) {
        tmp = array[i];
        array[i] = array[largest];
        array[largest] = tmp;

        max_heapify(array,largest,heap_size);
    }
}

void build_max_heap(int array[], int heap_size)
{
    int index;

    for(index = heap_size/2; index >= 1; index--) {
        max_heapify(array,index,heap_size);
    }
}

void heap_sort(int array[], int heap_size)
{
    int i, tmp;
    build_max_heap(array,heap_size);

    for(i = heap_size; i >= 1; i--) {
        tmp = array[i];
        array[i] = array[1];
        array[1] = tmp;

        heap_size--;
        max_heapify(array,1,heap_size);
    }
}

int main()
{
    int index;
    int array[6] = {0,1,5,2,4,3};

    for(index = 1; index < 6; index++) {
        printf("%2d",array[index]);
    }
    printf("\n");

    heap_sort(array,5);

    for(index = 1; index < 6; index++) {
        printf("%2d",array[index]);
    }
    printf("\n");

}
 复杂度：O(nlgn)
         建堆：O（n), 调整：(n-1)*O(lgn)