#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
#define minnum -1000
typedef struct tnode* hmnode;
struct tnode{
	int weight;
	hmnode left;
	hmnode right;
};
typedef struct heap* minheap;
struct heap{
	hmnode* data;
	int capacity;
	int size;
};
hmnode createnode(int w){
	hmnode ret=(hmnode)malloc(sizeof(struct tnode));
	ret->weight=w;
	ret->left=NULL;
	ret->right=NULL;
	return ret;
}
minheap createheap(){
	minheap ret=(minheap)malloc(sizeof(struct heap));
	ret->capacity=maxsize;
	ret->size=0;
	ret->data=(hmnode*)malloc(sizeof(hmnode)*(ret->capacity+1));
	ret->data[0]=createnode(minnum);
	return ret;
}
minheap insert(minheap h,hmnode x){
	if(h->size==h->capacity){
		printf("堆满！");
	}else{
		h->data[++h->size]=x;
		int child=h->size;
		int parent=child/2;
		while(h->data[child]->weight<h->data[parent]->weight){
			hmnode temp=h->data[child];
			h->data[child]=h->data[parent];
			h->data[parent]=temp;
			child=parent;
			parent=child/2;
		}
	}
	return h;
}
hmnode del(minheap h){
	hmnode ret=NULL;
	if(h->size){
		ret=h->data[1];
		h->data[1]=h->data[h->size--];
		int parent=1;
		int child=parent*2;
		for(;child<=h->size;){
			int min=h->data[child]->weight;
			int pos=child;//默认左儿子最小；
			if(child+1<=h->size&&h->data[child+1]->weight<h->data[child]->weight){
				min=h->data[child+1]->weight;
				pos=child+1;
			}
			if(h->data[parent]->weight>min){
				hmnode temp=h->data[parent];
				h->data[parent]=h->data[pos];
				h->data[pos]=temp;
				parent=pos;
				child=2*parent;
			}
			
		}
	}else{
		printf("堆空!");
	}
	return ret;
}
hmnode createtree(int * list,int size){
	minheap h=createheap();
	int i;
	for(i=0;i<size;i++){
		insert(h,createnode(list[i]));
	}
	while(h->size>1){
		hmnode a=del(h);
		hmnode b=del(h);
		hmnode c=createnode(a->weight+b->weight);
		c->left=a;
		c->right=b;
		insert(h,c);
	}
	return h->data[1];	
}
void traversal(hmnode t){
	if(t){
		printf("(%d)\n",t->weight);
		traversal(t->left);
		traversal(t->right);
	}
}
int main(){
	int a[]={1,2,3,4,5};
	hmnode t=createtree(a,5);
	traversal(t);
	return 0;
}