class my_heap//最小堆
{
public:
int h[maxn];
int size;
my_heap()
{
size=0;
}
void siftdown(int start,int end)//下移
{
int i=start,j=2*i+1,buf=h[i];
while(j<=end)
{
if(j<end&&h[j]>h[j+1]) j++;
if(h[j]>=buf) break;
else
{
h[i]=h[j];
i=j;
j=2*j+1;
}
h[i]=buf;
}
}
void siftup(int pos)//上移
{
int i=pos,j=(i-1)/2,temp=h[i];
while(i>0)
{
if(h[j]<=temp) break;
else
{
h[i]=h[j];
i=j;
j=(j-1)>>1;
}
h[i]=temp;
}
}
void insert(int elem)//插入
{
h[size]=elem;
siftup(size);
size++;
}
void remove_min()//删除最小值
{
if(size<=1)
{
size--;
return ;
}
swap(h[0],h[size-1]);
size--;
siftdown(0,size-1);
}
void intial()//建立堆
{
int pos=(size-2)>>1;
while(pos>=0)
{
siftdown(pos,size-1);
pos--;
}
}
void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void heap_sort()//堆的初始化
{
int len=size;
intial();
while(len>1)
{
swap(h[0],h[len-1]);
len--;
siftdown(0,len-1);
}
printf("sorted heap\n");
for(int i=0;i<size;i++)
{
printf("%d ",h[i]);
}
}
void input()
{
printf("input the size\n");
scanf("%d",&size);
printf("input the number\n");
for(int i=0;i<size;i++)
{
scanf("%d",&h[i]);
}
}
}; posted on 2011-02-13 13:46
avcpp 阅读(89)
评论(0) 编辑 收藏 引用