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