堆排序heapsortC语言实现

#include <stdio.h>

#define SIZE 10        

#define Left(i)        ((i) << 1)        
#define Right(i)    (((i) << 1) + 1)

void heapsort(int a[], int heapsize);
void maxheapify(int a[], int i, int heapsize);
void swap(int *x, int *y);

int main(int argc, char **argv)
{
    int a[SIZE+1] = { 0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };    
    /* note a[0] is not used */
    int i, heapsize;

    heapsize = SIZE;
    heapsort(a, heapsize);

    for (i = 1; i < SIZE + 1; i++)        /* print the sorted array */
        printf("%d ", a[i]);
    printf("\n");

    return 1;
}

/*
 * heapsort: contains two procedures, one is to build the max-heap,
 * the other is to delete max to gain the sorted array.
 */
void heapsort(int a[], int heapsize)
{
    int i;

    for (i = heapsize / 2; i >= 1; i--)        /* build max-heap */
        maxheapify(a, i, heapsize);        

    for (i = heapsize; i >= 2; i--)            /* delete max */    
    {
        swap(&a[1], &a[i]);
        heapsize--;
        maxheapify(a, 1, heapsize);
    }

}

/*
 * maxheapify: used to let the value at a[i] "float down" in the
 * max-heap so that the subtree rooted at index i becomes a max-heap.
 */
void maxheapify(int a[], int i, int heapsize)
{
    int largest, left, right;

    left = Left(i);
    right = Right(i);

    if (left <= heapsize && a[left] > a[i])
        largest = left;
    else
        largest = i;
    if (right <= heapsize && a[right] > a[largest])
        largest = right;

    if (largest != i)
    {
        swap(&a[i], &a[largest]);
        maxheapify(a, largest, heapsize);    /* recurrsion */
    }

    return;        /* return when largest == i */
}

void swap(int *x, int *y)
{
    int temp;

    temp = *x;
    *x = *y;
    *y = temp;
}