学步园

#include <stdio.h>

#define UINT32 unsigned int

#define HEAP_SIZE   (10)

#define PARENT(i) (i >> 1)
#define LEFT(i) (i << 1)
#define RIGHT(i) ((i << 1) + 1)

static void print_heap(UINT32 a_heap[], UINT32 heap_size)
{
    UINT32 i = 0;

    if (NULL == a_heap)
    {
        printf("ERROR: a_heap is NULL\n");
        return;
    }

    if (heap_size <= 0)
    {
        printf("ERROR: heap_size is ERR\n");
        return;
    }

    for (i = 1; i <= heap_size; i++)
    {
        printf("%d ", a_heap[i]);
    }
    printf("\n");

}

static void max_heapify(UINT32 a_heap[], UINT32 heap_size, UINT32 i)
{
    UINT32 left = LEFT(i);
    UINT32 right = RIGHT(i);
    UINT32 largest = 0;
    UINT32 temp = 0;

    if (NULL == a_heap)
    {
        printf("ERROR: a_heap is NULL!\n");
        return;
    }

    if (i <= 0 || i > heap_size)
    {
        return;
    }

    if (left <= heap_size && left > 0)
    {
        if (a_heap[left] > a_heap[i])
        {
            largest = left;
        }else{
            largest = i;
        }
    }

    if (right <= heap_size && right > 0)

    {
        if (a_heap[right] > a_heap[largest])
        {
            largest = right;
        }
    }

    if (largest <= heap_size
            && largest > 0
            && largest != i)
    {
        temp = a_heap[i];
        a_heap[i] = a_heap[largest];
        a_heap[largest] = temp;
        max_heapify(a_heap, heap_size, largest);
    }
}

/* 建堆 */
static void build_max_heap(UINT32 a_heap[], UINT32 heap_size)
{
    UINT32 i = 0;

    for (i = heap_size / 2; i >= 1; i--)
    {
        max_heapify(a_heap, heap_size, i);
    }
}

/* 堆排序 */
static void heap_sort(UINT32 a_heap[], UINT32 heap_size)
{
    UINT32 i = 0;

    UINT32 temp = 0;

    build_max_heap(a_heap, heap_size);

    for (i = heap_size; i >= 2; i--)
    {
        temp = a_heap[i];
        a_heap[i] = a_heap[1];
        a_heap[1] = temp;
        heap_size--;
        max_heapify(a_heap, heap_size, 1);
    }

}

int main(void)
{
    UINT32 a_heap[HEAP_SIZE + 1] = {0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    UINT32 heap_size = HEAP_SIZE;

    print_heap(a_heap, heap_size);
    heap_sort(a_heap, heap_size);
    print_heap(a_heap, heap_size);

    return 0;
}