Sunday, August 13, 2006

algorithms for heap-sort

here is the algorithms for heap-sort,which is another solution for the sorting,better than insertion-sort,equal to merge-sort.
there are several subroutines assisting heap-sort;
one is max-heapify:
procedure max-heapify(A,i,length_A) //to make subtree i to fit the properties of max-heap;
l=2*i; //left child;
r=2*i+1; //right child;
if(lA[i])
__largest=l;
else
__largest=i;
if(rA[largest])
__largest=r;
if(largest!=i) {
__tmp=A[i];
__A[i]=A[largest];
__A[largest]=tmp;
__max-heapify(A,largest,length_A);
}
end procedure;

one is build-max-heap;
procedure build-max-heap(A,length_A)
for(i=(int)(length_A/2);i>=0;i--)
__max-heapify(A,i,length_A);
end procedure;

with these two subroutines,we can define the algorithms for heapsort;
procedure heap-sort(A,length_A)
build-max-heap(A,length_A);
for(i=length_A-1;i>0;i--){
__tmp = A[i];
__A[1] = A[0];
__A[0] = tmp;
__max-heapify(A,i,length_A-1);
}
end procedure;

0 Comments:

Post a Comment

<< Home