#include <stdio.h>
#include <stdlib.h>
void MaxHeapify(int a[],int length,int i);
void BuildMaxHeapify(int a[],int length);
void HeapSort(int a[],int length);
void main(void)
{
int i;
int a[10]={1,3,4,2,1,3,2,19,4,0};
printf("Heapsort algorithm\n");
HeapSort(a,10);
for(i=0;i<10;i++)
printf("%d\n",a[i]);
while(1);
}
//在i的左右都满足最大堆性质时,使数组中下标为i的节点满足最大堆性质
void MaxHeapify(int a[],int length,int i)
{
int l = 2*i + 1; //左节点数组下标
int r = 2*i + 2; //右节点数组下表
int tmp = 0;
int largest = i;
if(l < length && a[i] < a[l])
largest = l;
if(r < length && a[r] > a[largest])
largest = r;
if(largest != i){
tmp = a[i];
a[i] = a[largest];
a[largest] = tmp;
MaxHeapify(a,length,largest);
}
return;
}
//使数组为最大堆,此时a[0]即为最大值
//采用自底向上方法构建最大堆,因为单独的叶节点一定满足最大堆性质
void BuildMaxHeapify(int a[],int length)
{
int i;
for(i=length/2-1; i>=0; i--){
MaxHeapify(a,length,i);
}
return;
}
//堆排序算法,首先构造最大堆,然后循环找到最大值
void HeapSort(int a[],int length)
{
int i,tmp;
BuildMaxHeapify(a,length); //此时为最大堆,最大值为a[0];
for(i=length-1; i>0; i--){
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
length--;
MaxHeapify(a,length,0);//注意该函数调用条件
}
}
vs2010已经调试成功。和算法导论描述一致。