Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3233663
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-02-27 18:28:59

#include
#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;
}
阅读(2181) | 评论(1) | 转发(1) |
0

上一篇:堆排序代码

下一篇:二项堆

给主人留下些什么吧!~~

chinaunix网友2011-03-05 16:30:42

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com