#include
#include
#include
#include
typedef struct __MaxHeap
{
int *heap;
int MaxSize;
int size;
}MaxHeap;
int InitMaxHeap(MaxHeap* pmaxheap,int maxsize)
{
pmaxheap->heap =(int*) malloc((maxsize+1)*sizeof(int));
if(pmaxheap->heap== NULL)
{
printf("Malloc failed \r\n");
return -1;
}
pmaxheap->size = 0;
pmaxheap->MaxSize = maxsize ;
return 0;
}
int exchange(int *a ,int *b)
{
int tmp;
if(*a != *b)
{
tmp = *a;
*a = *b;
*b = tmp;
}
return 0;
}
int FixUp(MaxHeap *pmaxheap,int pos)
{
int idx = pos;
int *heap = pmaxheap->heap;
while(idx >1 && *(heap+idx/2) < *(heap+idx))
{
exchange(heap+idx/2,heap+idx);
idx/=2;
}
return 0;
}
int FixDown(MaxHeap *pmaxheap,int pos)
{
int j ;
int k = pos;
int *heap = pmaxheap->heap;
while(2*k <= pmaxheap->size)
{
j = 2*k;
if(j< pmaxheap->size && *(heap+j) < *(heap+j+1))
{
j++;
}
if (*(heap+k) > *(heap+j))
break;
else
{
exchange(heap+k,heap+j);
k = j;
}
}
return 0;
}
int MaxHeap_Insert(MaxHeap *pmaxheap,int newitem)
{
int size;
pmaxheap->size++;
size = pmaxheap->size;
pmaxheap->heap[size] = newitem;
FixUp(pmaxheap,size);
return 0;
}
int MaxHeap_DelMax(MaxHeap *pmaxheap,int* max)
{
if(pmaxheap->size < 1)
{
printf(" heap downflowed\r\n");
return -1;
}
*max = pmaxheap->heap[1];
exchange(&(pmaxheap->heap[1]),&(pmaxheap->heap[pmaxheap->size]));
pmaxheap->size--;
FixDown(pmaxheap,1);
return 0;
}
int heapsort(int *array,int l,int r)
{
int k ;
int cap = r- l+1;
MaxHeap maxheap;
InitMaxHeap(&maxheap,cap);
for(k = l ;k<=r ; k++)
{
MaxHeap_Insert(&maxheap,array[k]);
}
for(k = r;k>=l;k--)
{
MaxHeap_DelMax(&maxheap,&array[k]);
}
return 0;
}
int test_heapsort()
{
int array[5] = {0};
int i;
srand(time(NULL));
for(i = 0;i<5;i++)
{
array[i] = rand()%100;
printf("%d\t",array[i]);
}
printf("\n");
heapsort(array,0,4);
for(i = 0;i<5;i++)
{
printf("%d\t",array[i]);
}
printf("\n");
return 0;
}
int test_initmaxheap()
{
MaxHeap maxheap;
if(InitMaxHeap(&maxheap,16)== 0)
{
assert(maxheap.MaxSize == 16);
assert(maxheap.size == 0);
}
return 0;
}
int test()
{
test_initmaxheap();
test_heapsort();
return 0;
}
int main()
{
test();
return 0;
}
