7-1 修理牧场
#include<stdio.h>
#include<stdlib.h>
struct HNode{
int * data;
int maxsize;
int size;
};
typedef HNode* MinTree;
/*创建一个空的最小堆*/
MinTree Creat(int max){
MinTree H = (MinTree)malloc(sizeof(struct HNode));
H->data = (int*)malloc((max+1)*sizeof(int));
H->size = 0;
H->maxsize = max;
H->data[0] = 0;
return H;
}
/*最小堆的插入*/
bool Insert(int x,MinTree H){
int i;
i = ++H->size;
for(;H->data[i/2]>x;i/=2){
H->data[i] = H->data[i/2];
}
H->data[i] = x;
return true;
}
/*最小堆的删除*/
void Dele(MinTree H){
int parent,child,x;
x = H->data[H->size--];
for(parent=1;parent*2<=H->size;parent=child){
child=parent*2;
if((child!=H->size)&&(H->data[child]>H->data[child+1])) //child！=H->size代表有右子树
child++; /*保证child指向左右节点的最小值*/
if(x<H->data[child]) break; //找到x的插入位置
else
H->data[parent] = H->data[child];//下滤x
}
H->data[parent] = x;
}
int main()
{
int n,a;
int sum = 0;
int res = 0;
scanf("%d",&n);
MinTree H = Creat(n);
for(int i=0;i<n;i++){
scanf("%d",&a);
Insert(a,H);
}
for(;H->size>1;){
if(H->size>2)
if(H->data[2]<H->data[3])
sum=H->data[1]+H->data[2]; /*将最小堆里面权值最小的两个相加*/
else
sum=H->data[1]+H->data[3];
else if(H->size=2)
sum = H->data[1]+H->data[2];
res+=sum;//即哈夫曼树的带权路径长度
Dele(H);//把相加过的权值从堆中删除
Dele(H);
Insert(sum,H);//把得到的新的权值插入堆中
sum = 0;
}
printf("%d",res);
return 0;
}
