安迪的找工作日志——算法基础学习之堆排序
堆定义：
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 堆总是满足下列性质：
堆中某个节点的值总是大于或小于其父节点的值；
堆总是一颗完全树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
如何建堆？
1）首先要说一下一个建堆的子过程，《算法导论》中将其称作MAX-HEAPIFY方法，其输入一个数组A以及一个下标i，并使得以i为根的子树成为最大堆。
这个的实现方法也很简单，就是从元素A[i],A[LEFT[i］和[RIGHT[i］中找出最大值，并将其下标标为largest。如果A[i]已经是最大的，则程序结束。否则，i的某个子节点有最大元素，将其与A[i]交换，从而使i与其子节点满足堆性质，接下来接着对交换过后的A[i]再次重复此操作，即递归调用MAX-HEAPIFY。
2）再考虑建堆
我们可以自底向上用MAX-HEAPIFY把数组A[1..n]变成一个大根堆。因为子数组A[floor(n/2)..n],floor指向下取整中的元素都是叶子结点，所以呢这些节点都可以看作是只含有一个元素的堆。所以我们可以从floor（n/2）开始，对数组中的每个其他元素都来调用一次max-heapify，这样就可以得到一个大根堆。（想想，后面的元素已经都是堆，再对前面的元素每个都执行max-heapify，这样一来，前面的所有节点为根的堆都成为了大根堆，整个数组当然也就是大根堆了）
具体实现（C语言版本，自己编写实现）：
//date:2012/9/14
//author：Andy
//description：build a heap
#include <stdio.h>
#include <stdlib.h>
//void max-heapify(int [],int);
void build_heap(int *,int);
void max_heapify(int *,int,int);
main()
{
int a[10] = {13,14,6,5,8,20,16,18,7,10};//test array
int length = 10;
int i = 0;
printf("The heap before building is:\n ");
for(;i < length;i++)
printf("%d ",a[i]);
build_heap(&a[0],length);
printf("\nThe heap after building is:\n ");
for(i = 0;i < length;i++)
printf("%d ",a[i]);
system("pause");
return 0;
}
void build_heap(int* a,int l){//build a heap based on the array and the length of the array passed in
int start = l / 2;
for (;start >= 0;start--){
max_heapify(&a[0],start,l);//for every element befor l/2,max_heapify it
}
}
void max_heapify(int *a,int i,int length){
int l = 2*i + 1;
int r = 2*i + 2;//left and right child of element i
int largest;
int temp;
if (l < length && a[l] > a[i]){
largest = l;
}else{
largest = i;
}
if (r < length && a[r] > a[largest]){
largest = r;
}
if (largest != i){
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(&a[0],largest,length);
}//if largest is not i,so we need to change the root of the heap and reverse call max-heapify
}
OK，堆建好了，那么剩下的就是堆排序了。
其实建好堆之后，堆排序也就完成了大半，剩下的堆排序的思路很简单。
就是将原来大根堆的第一个元素（数组中最大的那个）与数组最后一个元素交换，对于前n-1个已被破坏的大根堆，只需要对其进行max-heapify就好了。然后重复此过程n-1遍，则得到的就是从小到大排列的元素。
当然，这里的代码相对于上面的建堆的代码有一点点小的变化，就是这个时候在max_heapify中左右孩子下标l和r应该是小于heapsize(a)，而不是整个数组的长度length。
自己编写的C语言实现堆排序：
//date:2012/9/14
//author：Andy
//description：build a heap
#include <stdio.h>
#include <stdlib.h>
//void max-heapify(int [],int);
void build_heap(int *,int);
void max_heapify(int *,int,int);
void heap_sort(int *,int);
//int heapSize;
main()
{
int a[10] = {13,14,6,5,8,20,16,18,7,10};//test array
int length = 10;
int i = 0;
printf("The heap before building is:\n ");
for(;i < length;i++)
printf("%d ",a[i]);
build_heap(&a[0],length);
printf("\nThe heap after building is:\n ");
for(i = 0;i < length;i++)
printf("%d ",a[i]);
//heapSize = length;
heap_sort(&a[0],length);
printf("\nThe heap after heap sort is:\n ");
for(i = 0;i < length;i++)
printf("%d ",a[i]);
system("pause");
return 0;
}
void heap_sort(int* a,int length){
int i;
int temp;
for (i = length;i > 1;i--){
temp = a[0];
a[0] = a[i-1];
a[i-1] = temp;
max_heapify(&a[0],0,i-1);
}
}
void build_heap(int* a,int l){//build a heap based on the array and the length of the array passed in
int start = l / 2;
for (;start >= 0;start--){
max_heapify(&a[0],start,l);//for every element befor l/2,max_heapify it
}
}
void max_heapify(int *a,int i,int length){
int l = 2*i + 1;
int r = 2*i + 2;//left and right child of element i
int largest;
int temp;
if (l < length && a[l] > a[i]){
largest = l;
}else{
largest = i;
}
if (r < length && a[r] > a[largest]){
largest = r;
}
if (largest != i){
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(&a[0],largest,length);
}//if largest is not i,so we need to change the root of the heap and reverse call max-heapify
}
这里对于传入max_heapify中的第三个变量，即此时堆的长度一定要非常小心，还有循环的次数，要是n-1次。不然堆排序出来的结果就会不正确。
ok，堆排序完成，下面分析小根堆建立优先队列：）
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 堆总是满足下列性质：
堆中某个节点的值总是大于或小于其父节点的值；
堆总是一颗完全树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
如何建堆？
1）首先要说一下一个建堆的子过程，《算法导论》中将其称作MAX-HEAPIFY方法，其输入一个数组A以及一个下标i，并使得以i为根的子树成为最大堆。
这个的实现方法也很简单，就是从元素A[i],A[LEFT[i］和[RIGHT[i］中找出最大值，并将其下标标为largest。如果A[i]已经是最大的，则程序结束。否则，i的某个子节点有最大元素，将其与A[i]交换，从而使i与其子节点满足堆性质，接下来接着对交换过后的A[i]再次重复此操作，即递归调用MAX-HEAPIFY。
2）再考虑建堆
我们可以自底向上用MAX-HEAPIFY把数组A[1..n]变成一个大根堆。因为子数组A[floor(n/2)..n],floor指向下取整中的元素都是叶子结点，所以呢这些节点都可以看作是只含有一个元素的堆。所以我们可以从floor（n/2）开始，对数组中的每个其他元素都来调用一次max-heapify，这样就可以得到一个大根堆。（想想，后面的元素已经都是堆，再对前面的元素每个都执行max-heapify，这样一来，前面的所有节点为根的堆都成为了大根堆，整个数组当然也就是大根堆了）
具体实现（C语言版本，自己编写实现）：
//date:2012/9/14
//author：Andy
//description：build a heap
#include <stdio.h>
#include <stdlib.h>
//void max-heapify(int [],int);
void build_heap(int *,int);
void max_heapify(int *,int,int);
main()
{
int a[10] = {13,14,6,5,8,20,16,18,7,10};//test array
int length = 10;
int i = 0;
printf("The heap before building is:\n ");
for(;i < length;i++)
printf("%d ",a[i]);
build_heap(&a[0],length);
printf("\nThe heap after building is:\n ");
for(i = 0;i < length;i++)
printf("%d ",a[i]);
system("pause");
return 0;
}
void build_heap(int* a,int l){//build a heap based on the array and the length of the array passed in
int start = l / 2;
for (;start >= 0;start--){
max_heapify(&a[0],start,l);//for every element befor l/2,max_heapify it
}
}
void max_heapify(int *a,int i,int length){
int l = 2*i + 1;
int r = 2*i + 2;//left and right child of element i
int largest;
int temp;
if (l < length && a[l] > a[i]){
largest = l;
}else{
largest = i;
}
if (r < length && a[r] > a[largest]){
largest = r;
}
if (largest != i){
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(&a[0],largest,length);
}//if largest is not i,so we need to change the root of the heap and reverse call max-heapify
}
OK，堆建好了，那么剩下的就是堆排序了。
其实建好堆之后，堆排序也就完成了大半，剩下的堆排序的思路很简单。
就是将原来大根堆的第一个元素（数组中最大的那个）与数组最后一个元素交换，对于前n-1个已被破坏的大根堆，只需要对其进行max-heapify就好了。然后重复此过程n-1遍，则得到的就是从小到大排列的元素。
当然，这里的代码相对于上面的建堆的代码有一点点小的变化，就是这个时候在max_heapify中左右孩子下标l和r应该是小于heapsize(a)，而不是整个数组的长度length。
自己编写的C语言实现堆排序：
//date:2012/9/14
//author：Andy
//description：build a heap
#include <stdio.h>
#include <stdlib.h>
//void max-heapify(int [],int);
void build_heap(int *,int);
void max_heapify(int *,int,int);
void heap_sort(int *,int);
//int heapSize;
main()
{
int a[10] = {13,14,6,5,8,20,16,18,7,10};//test array
int length = 10;
int i = 0;
printf("The heap before building is:\n ");
for(;i < length;i++)
printf("%d ",a[i]);
build_heap(&a[0],length);
printf("\nThe heap after building is:\n ");
for(i = 0;i < length;i++)
printf("%d ",a[i]);
//heapSize = length;
heap_sort(&a[0],length);
printf("\nThe heap after heap sort is:\n ");
for(i = 0;i < length;i++)
printf("%d ",a[i]);
system("pause");
return 0;
}
void heap_sort(int* a,int length){
int i;
int temp;
for (i = length;i > 1;i--){
temp = a[0];
a[0] = a[i-1];
a[i-1] = temp;
max_heapify(&a[0],0,i-1);
}
}
void build_heap(int* a,int l){//build a heap based on the array and the length of the array passed in
int start = l / 2;
for (;start >= 0;start--){
max_heapify(&a[0],start,l);//for every element befor l/2,max_heapify it
}
}
void max_heapify(int *a,int i,int length){
int l = 2*i + 1;
int r = 2*i + 2;//left and right child of element i
int largest;
int temp;
if (l < length && a[l] > a[i]){
largest = l;
}else{
largest = i;
}
if (r < length && a[r] > a[largest]){
largest = r;
}
if (largest != i){
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(&a[0],largest,length);
}//if largest is not i,so we need to change the root of the heap and reverse call max-heapify
}
这里对于传入max_heapify中的第三个变量，即此时堆的长度一定要非常小心，还有循环的次数，要是n-1次。不然堆排序出来的结果就会不正确。
ok，堆排序完成，下面分析小根堆建立优先队列：）
