堆
堆是一个完全二叉树的数组对象。树的每一层都是满的，最后一层可能除外（因为从一个节点的左子树开始填）。
例如
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");
}
