堆

堆是一個(gè)完全二叉樹的數(shù)組對象。樹的每一層都是滿的，最后一層可能除外（因?yàn)閺囊粋€(gè)節(jié)點(diǎn)的左子樹開始填）。

例如

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

節(jié)點(diǎn)位置計(jì)算

給定一個(gè)節(jié)點(diǎn)，可以很容易的計(jì)算父節(jié)點(diǎn)和子節(jié)點(diǎn)的位置。
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

堆排序

堆排序的時(shí)間復(fù)雜度為O(nlogn)是比較有效率的一種。其使用的是最大堆。最大堆的意思是父節(jié)點(diǎn)的值>=孩子節(jié)點(diǎn)的值。所以，堆排序每次循環(huán)把最大值移走，然后從剩下的節(jié)點(diǎn)重新建立最大堆。

第一步：

首先定義堆的結(jié)構(gòu)體

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指針指向的是存放堆數(shù)據(jù)的數(shù)組。
heapMaxIndex是堆的最大序號。比它小的都屬于堆。
arrLength是數(shù)組最大的序號。如數(shù)組定義為a[10]，那么arrLength的值應(yīng)該為9。

第二步：

保持堆的性質(zhì)
這一步是堆排序的基礎(chǔ)。這里將功能寫成一個(gè)函數(shù)名為void maxHeapify(Heap *hp, unsigned int nodei)，這個(gè)函數(shù)用于讓一個(gè)數(shù)組變成一個(gè)符合堆性質(zhì)的數(shù)組。時(shí)間復(fù)雜度為O(h)，h是堆所屬二叉樹的高度=logn(n是節(jié)點(diǎn)個(gè)數(shù))。
思想：
從一個(gè)節(jié)點(diǎn)i，和它的孩子leftChild(i)和rightChild(i)中找到最大的，然后其索引存放在largest中。如果i的值是最大的。那么i為根的子樹已經(jīng)是最大堆，程序結(jié)束。
如果i的值不是最大的，那么將i的值和largest的值交換。下標(biāo)為largest的節(jié)點(diǎn)在交換后作為父節(jié)點(diǎn)，那么它有可能違反堆的性質(zhì)，因此遞歸調(diào)用該函數(shù)。

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函數(shù)創(chuàng)建堆

對于1個(gè)size為n的堆，我們可以分析到，n/2-1之前的都是父節(jié)點(diǎn)，其他的都是葉子節(jié)點(diǎn)，我們只需要對父節(jié)點(diǎn)進(jìn)行maxHeapify就可以了。
n/2可以用右移運(yùn)算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;
}

第四步 堆排序

設(shè)堆的數(shù)組為A[0..n-1]，調(diào)用maxHeapify函數(shù)就可以得到最大值，然后將最大值和n-1互換，把堆的大小heapMaxIndex減1，再次調(diào)用maxHeapify，又得到最大值，存放在A[0]，再和A[n-2]互換，把堆的大小再減一，這樣循環(huán)下去，直到堆的大小為0。那么我們就得到了從小到大的排好序的數(shù)組。

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");
}