[code=Cpp width=740px]// Author: Ahalei
// Date: 11 6, 2010
// City: Wuhan
// Website: www.ahalei.com
// Title: Heap(最大堆)
#include <stdio.h>
int h[101];//用来存放堆的数组
int n;//用来存储堆中元素的个数,也就是堆的大小
//交换函数,用来交换堆中的两个元素的值
void swap(int x,int y)
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}
//求最大值函数,用来返回a和b中较大的一个
int max(int a,int b)
{
return a>b?a:b;//这是一个三目运算符,如何使用请问baidu
}
//向上调整函数
void siftup(int i)
{
int flag=0;//用来标记是否仍然需要继续调整
//如果是堆顶,就返回,不需要调整了
if(i==1)
return;
//不在堆顶 并且 他比爸爸大的时候 继续调整
while(i!=1 && flag==0)
{
//看看他的是否比他的爸爸大
if(h>h[i/2])
swap(i,i/2);//交换他和他爸爸的位置
else
flag=1;//表示当前已经不需要调整了,已经符合堆得结构,他比他爸爸小了
i=i/2;//这句话很重要,对他的爸爸继续进行调整
}
}
//向下调整函数
void siftdown()
{
int flag=0,t,i;//用来标记是否仍然需要继续调整
//堆的顶点开始向下调整
i=1;
//当他至少有左儿子的时候 并且仍然 有需要继续调整的时候循环
while( 2*i<=n && flag==0)
{
//首先判断他和他左儿子的关系
if( h < h[i*2] )
t=i*2;//记录值较大的节点编号
else
t=i;//记录值较大的节点编号
//如果他有右儿子的情况下,再对右儿子进行讨论
if(i*2+1 <= n)
{
//首先判断他和他右儿子的关系
if(h[t] < h[i*2+1])
t=i*2+1;//记录值较大的节点编号
}
//如果最大的节点编号不是自己,也就是说他的孩子中有比他大的
if(t!=i)
{
swap(t,i);//交换他们
i=t;//更新i为他的孩子的编号,继续向下调整
}
else
flag=1;//则否说明当前的爸爸已经比两个孩子都要大了,不需要在进行调整了
}
}
//建立堆的函数
void creat()
{
int i;
//从最后一个节点到第一个节点进行向上调整
for(i=n;i>=1;i--)
{
siftup(i);
}
}
//删除最大的元素
int deletemax()
{
int t;
t=h[1];//用一个临时变量记录堆顶点的值
h[1]=h[n];//将堆得最后一个点赋值到堆顶
n--;//堆的元素减少1
siftdown();//向下调整
return t;//返回之前记录的堆得顶点的最大值
}
int main()
{
int i,num;
//读入n个数
scanf("%d",&num);
n=num;
for(i=1;i<=num;i++)
scanf("%d",&h);
//建堆
creat();
//删除顶部元素,连续删除n次,其实夜就是从大到小把数输出来
for(i=1;i<=num;i++)
printf("%d ",deletemax());
getchar();
getchar();
return 0;
}
</stdio.h>[/code]
|