2011-10-06 16:00:43

#include <stdio.h>

const int Length = 10; //堆大小

void Max_Heapify(int [], int, int);

void Build_Max_Heap(int []);

void HeapSort(int [], int);

/*单一子节点最大堆调整*/

void Max_Heapify(int L[], int i, int length)

int l = 2*i+1;/*根节点为0时，i的左子节点*/

int r = 2*i+2;/*右子节点*/

int largest;

int temp;

if(l < length && L[l] > L[i])

{

largest = l;

}

else

{

largest = i;

}

if(r < length && L[r] > L[largest])

{

largest = r;

}

if(largest != i)

{

temp = L[i];

L[i] = L[largest];

L[largest] = temp;

Max_Heapify(L, largest, length);//交换后的子节点比父节点小，

//但不能保证交换过来的子节点比他的子节点小，所以要递归，使子节点为根的子树也是最大堆

}

/*建立初始最大堆*/

void Build_Max_Heap(int L[])

int i,j;

for(i = Length/2; i >= 0; i--)

{

Max_Heapify(L, i, Length);

}

/*堆排序*/

void HeapSort(int L[], int length)

int temp;

int i;

Build_Max_Heap(L);

for(i = length - 1; i >= 1; i--)

{

temp = L[0];// 交换堆顶和堆尾，取得最大值

L[0] = L[i];

L[i] = temp;

length = length - 1;//整个数组元素个数减1

Max_Heapify(L, 0, length);//对新数组生成最大堆

}

for(i = 0; i < Length;i++)

{

printf("%d ", L[i]);

}

printf("\n");

int main()

int L[10]={4,9,2,6,0,8,3,7,5,1},i;

HeapSort(L, Length);

system("pause");

return 0;

creat by 张飞雪