#include <stdio.h>
#include <stdlib.h>
int heapsize;
void Heapify(int *A,int i)
{
int l,r;
l=2*i+1;
r=2*i+2;
int max;
if(l<=heapsize&&A[l]>A[i])
max = l;
else
max=i;
if(r<=heapsize&&A[r]>A[max])
max = r;
if(max!=i)
{
int temp;
temp=A[i];
A[i]=A[max];
A[max]=temp;
Heapify(A,max);
}
}
void Buildheap(int *A)
{
int i;
heapsize = 10-1;
for(i=(10-1)/2;i>=0;i--)
{
Heapify(A,i);
}
}
void Heapsort(int *A)
{
Buildheap(A);
int i;
for(i=9;i>0;i--)
{
int swap;
swap = A[heapsize];
A[heapsize]=A[0];
A[0]=swap;
heapsize--;
Heapify(A,0);
}
}
int main()
{
int A[10] = {1,4,2,6,7,5,8,2,555,3};
Heapsort(A);
int i;
for(i = 0; i < 10; i++)
printf("%d ",A[i]);
return 0;
}
#include <stdlib.h>
int heapsize;
void Heapify(int *A,int i)
{
int l,r;
l=2*i+1;
r=2*i+2;
int max;
if(l<=heapsize&&A[l]>A[i])
max = l;
else
max=i;
if(r<=heapsize&&A[r]>A[max])
max = r;
if(max!=i)
{
int temp;
temp=A[i];
A[i]=A[max];
A[max]=temp;
Heapify(A,max);
}
}
void Buildheap(int *A)
{
int i;
heapsize = 10-1;
for(i=(10-1)/2;i>=0;i--)
{
Heapify(A,i);
}
}
void Heapsort(int *A)
{
Buildheap(A);
int i;
for(i=9;i>0;i--)
{
int swap;
swap = A[heapsize];
A[heapsize]=A[0];
A[0]=swap;
heapsize--;
Heapify(A,0);
}
}
int main()
{
int A[10] = {1,4,2,6,7,5,8,2,555,3};
Heapsort(A);
int i;
for(i = 0; i < 10; i++)
printf("%d ",A[i]);
return 0;
}
0 comments:
Post a Comment