堆排序

堆

堆是一个完全二叉树的数组对象。树的每一层都是满的，最后一层可能除外（因为从一个节点的左子树开始填）。

例如

0-1-2-3-4(索引)
16-14-10-2-1(值)

节点位置计算

给定一个节点，可以很容易的计算父节点和子节点的位置。
parent(i)=floor((i-1)/2)
leftChild=2(i+1)-1
rightChild=2(i+1)
注意：可以将乘2算法变成向左移位，除2算法变成向右移位。
即：
parent(i)=(i-1)>>1
leftChild=(i+1)<<1-1
rightChild=(i+1)<<1

堆排序

堆排序的时间复杂度为O(nlogn)是比较有效率的一种。其使用的是最大堆。最大堆的意思是父节点的值>=孩子节点的值。所以，堆排序每次循环把最大值移走，然后从剩下的节点重新建立最大堆。

第一步：

首先定义堆的结构体

typedef struct heap_t{
    int *arr;//point for an array to store heap value.
    int heapMaxIndex;//heap element max index number
    int arrLength;//array length of arr
} Heap;

其中arr指针指向的是存放堆数据的数组。
heapMaxIndex是堆的最大序号。比它小的都属于堆。
arrLength是数组最大的序号。如数组定义为a[10]，那么arrLength的值应该为9。

第二步：

保持堆的性质
这一步是堆排序的基础。这里将功能写成一个函数名为void maxHeapify(Heap *hp, unsigned int nodei)，这个函数用于让一个数组变成一个符合堆性质的数组。时间复杂度为O(h)，h是堆所属二叉树的高度=logn(n是节点个数)。
思想：
从一个节点i，和它的孩子leftChild(i)和rightChild(i)中找到最大的，然后其索引存放在largest中。如果i的值是最大的。那么i为根的子树已经是最大堆，程序结束。
如果i的值不是最大的，那么将i的值和largest的值交换。下标为largest的节点在交换后作为父节点，那么它有可能违反堆的性质，因此递归调用该函数。

void maxHeapify(Heap *hp, unsigned int nodei) {
    unsigned int l = (nodei + 1) << 1 - 1;//left child
    unsigned int r = (nodei + 1) << 1;//right child
    unsigned int largest = 0;
    int heapMaxI = hp->heapMaxIndex;
    if(l <= heapMaxI && hp->arr[l] > hp->arr[nodei])
        largest = l;
    else
        largest = nodei;
    if(r <= heapMaxI && hp->arr[r] > hp->arr[largest])
        largest = r;

    if(largest!=nodei) {
        swap(&(hp->arr[largest]), &(hp->arr[nodei]));
        maxHeapify(hp, largest);
    } else
        return ;
}

第三步 利用maxHeapify函数创建堆

对于1个size为n的堆，我们可以分析到，n/2-1之前的都是父节点，其他的都是叶子节点，我们只需要对父节点进行maxHeapify就可以了。
n/2可以用右移运算n>>1。

Heap* createHeap(int* arrp,int  arrMaxIndex, int arrLength) {
    Heap* heap = malloc(sizeof(Heap));
    assert(heap!=NULL);
    heap->arr = arrp;
    heap->heapMaxIndex = arrMaxIndex;
    heap->arrLength = arrLength;
    int i;
    for(i = (arrMaxIndex + 1) >> 1 - 1; i >=0; i--)
        maxHeapify(heap, i);
    return heap;
}

第四步 堆排序

设堆的数组为A[0..n-1]，调用maxHeapify函数就可以得到最大值，然后将最大值和n-1互换，把堆的大小heapMaxIndex减1，再次调用maxHeapify，又得到最大值，存放在A[0]，再和A[n-2]互换，把堆的大小再减一，这样循环下去，直到堆的大小为0。那么我们就得到了从小到大的排好序的数组。

void heapSort(Heap* hp) {
    int last;
    while(hp->heapMaxIndex > 0) {
        last = hp->heapMaxIndex;
        swap(&(hp->arr[0]), &(hp->arr[last]));
        hp->heapMaxIndex -= 1;
        maxHeapify(hp, 0);
    }
}

第五步 测试堆排序

int main(void) {
    int array[] = {15,25,32,23,1,-4,35,2,-85,42,0,12,26,56,45,12,145,17,25,21};
    printArr(array, getSize(array));
    Heap* hp = createHeap(array, getSize(array)-1, getSize(array));
    heapSort(hp);
    printArr(array, getSize(array));
    freeHeap(hp);
    return 0;
}

完整的程序如下

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct heap_t{
    int *arr;//point for an array to store heap value.
    int heapMaxIndex;//heap element max index number
    int arrLength;//array length of arr
} Heap;
#define getSize(array) (sizeof array / sizeof *array)
Heap* createHeap(int* arrp,int  arrMaxIndex, int arrLength);
void swap(int* a, int* b);
void heapSort(Heap* hp);
void freeHeap(Heap* heap);
void maxHeapify(Heap *hp, unsigned int nodei);
void printArr(int *p, int size);
int main(void) {
    int array[] = {15,25,32,23,1,-4,35,2,-85,42,0,12,26,56,45,12,145,17,25,21};
    printArr(array, getSize(array));
    Heap* hp = createHeap(array, getSize(array)-1, getSize(array));
    heapSort(hp);
    printArr(array, getSize(array));
    freeHeap(hp);
    return 0;
}

void swap(int* a, int* b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

Heap* createHeap(int* arrp,int  arrMaxIndex, int arrLength) {
    Heap* heap = malloc(sizeof(Heap));
    assert(heap!=NULL);
    heap->arr = arrp;
    heap->heapMaxIndex = arrMaxIndex;
    heap->arrLength = arrLength;
    int i;
    for(i = (arrMaxIndex + 1) >> 1 - 1; i >=0; i--)
        maxHeapify(heap, i);
    return heap;
}

void heapSort(Heap* hp) {
    int last;
    while(hp->heapMaxIndex > 0) {
        last = hp->heapMaxIndex;
        swap(&(hp->arr[0]), &(hp->arr[last]));
        hp->heapMaxIndex -= 1;
        maxHeapify(hp, 0);
    }
}

void freeHeap(Heap* heap) {
    free(heap);
}

void maxHeapify(Heap *hp, unsigned int nodei) {
    unsigned int l = (nodei + 1) << 1 - 1;//left child
    unsigned int r = (nodei + 1) << 1;//right child
    unsigned int largest = 0;
    int heapMaxI = hp->heapMaxIndex;
    if(l <= heapMaxI && hp->arr[l] > hp->arr[nodei])
        largest = l;
    else
        largest = nodei;
    if(r <= heapMaxI && hp->arr[r] > hp->arr[largest])
        largest = r;

    if(largest!=nodei) {
        swap(&(hp->arr[largest]), &(hp->arr[nodei]));
        maxHeapify(hp, largest);
    } else
        return ;
}
void printArr(int *p, int size) {
    int i;
    for(i = 0; i < size; i++) {
        printf("%d ", p[i]);
    }
    printf("\n");
}