堆排序

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：

由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。

堆的操作一般包括初始化、插入和删除：

下面是堆的简单实现：

typedef struct struct_heap {

    int size;
    int head;
    int *data;
}heap_t;

void initHeap(heap_t **heap, int size)
{
    heap_t *pHeap;

    pHeap = (heap_t*)malloc(sizeof(*pHeap) + size * sizeof(int));
    if (NULL == pHeap)
    {
        printf("malloc fail\n");
        return;
    }
    memset(pHeap, 0, sizeof(*pHeap) + size * sizeof(int));

    pHeap->size = size;
    pHeap->head = 0;
    pHeap->data = (int *) ((char *)pHeap + sizeof(*pHeap));

    *heap = pHeap;
}

void insertHeap(heap_t *pHeap, int key)
{
    int cursor;
    int tmp;

    if (NULL == pHeap)
        return;

    if (pHeap->head == pHeap->size)
    {
        printf("Heap is full\n");
        return;
    }

    pHeap->data[pHeap->head++] = key;

    cursor = pHeap->head - 1;

    while (cursor > 0)
    {
        if (pHeap->data[cursor] < pHeap->data[(cursor - 1)/2])
        {
            tmp = pHeap->data[cursor];
            pHeap->data[cursor] = pHeap->data[(cursor-1) /2];
            pHeap->data[(cursor-1) / 2] = tmp;
            cursor = (cursor - 1) / 2;
        }
        else
            break;
    }
}

void deleteHeap(heap_t *pHeap, int *out)
{
    int cursor;
    int temp;
    int left;
    int right;
    int key;

    if (NULL == pHeap)
        return;

    if (pHeap->head == 0)
    {
        printf("Heap is empty\n");
        return;
    }

    *out = pHeap->data[0];
    pHeap->data[0] = pHeap->data[pHeap->head - 1];
    pHeap->head--;

    cursor = 0;
    while (cursor < pHeap->head -1)
    {
        key = pHeap->data[cursor];
        left = key < 0 ? (key * -2) : (key * 2 + 1);
        right = left + 1;

        if ( (2 * cursor +1) <= pHeap->head -1)
        {
            left = pHeap->data[2*cursor +1];
        }
        if ( (2 * cursor +2) <= pHeap->head -1)
        {
            right = pHeap->data[2*cursor +2];
        }

        if (key > left && left < right)
        {
            temp = pHeap->data[cursor];
            pHeap->data[cursor] = pHeap->data[2 * cursor + 1];
            pHeap->data[2 * cursor + 1] = temp;
            cursor = 2 * cursor + 1;
        }
        else if (key > right && right < left)
        {
            temp = pHeap->data[cursor];
            pHeap->data[cursor] = pHeap->data[2 * cursor + 2];
            pHeap->data[2 * cursor + 2] = temp;
            cursor = 2 * cursor + 2;
        }
        else
            break;
    }
}

堆排序
理解堆的插入和删除后，堆排序实现就非常简单了。下面是堆排序的简单实现：

// 在index位置插入新元素后，修正堆序列使之满足堆要求
static void minHeapFixup(int list[], int index)
{
    int cursor;
    int temp;

    cursor = index;
    while (cursor > 0)
    {
        if (list[cursor] < list[(cursor -1)/2])
        {
            temp = list[cursor];
            list[cursor] = list[(cursor-1)/2];
            list[(cursor-1)/2] = temp;
            cursor = (cursor - 1) / 2;
        }
        else
            break;
    }
}

// 删除堆顶元素后，将最后一个元素移至堆顶，修正堆序列使之满足堆要求
static void minHeapFixdown(int list[], int len)
{
    int cursor;
    int temp;

    int key;
    int left;
    int right;

    cursor = 0;

    while (cursor < len)
    {
        key = list[cursor];

        if ( 2 * cursor + 1 < len)
            left = list[2 * cursor + 1];
        else
            left = key + 1;

        if ( 2 * cursor +2 < len)
            right = list[2 * cursor + 2];
        else
            right = key + 2;

        if (key > left && left < right)
        {
            temp = key;
            list[cursor] = left;
            list[cursor * 2 + 1] = temp;
            cursor = cursor * 2 + 1;
        }
        else if (key > right && right < left)
        {
            temp = key;
            list[cursor] = right;
            list[cursor * 2 + 2] = temp;
            cursor = cursor * 2 + 2;
        }
        else
            break;
    }
}

void heapSort(int list[], int len)
{
    int i;
    int temp;

    for (i = 1; i < len; i++)
        minHeapFixup(list, i);

    for (i = len; i > 1; i--)
    {
        temp = list[0];
        list[0] = list[i - 1];
        list[i - 1] = temp;

        minHeapFixdown(list, i - 1);
    }
}

注意这里采用的是最小堆，排序后数组是按递减顺序排列的；如果需要递增顺序，修改为最大堆，或者再进行一次倒置。