#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
#define hugenum 1000
typedef struct heapstruct* maxheap;
struct heapstruct{
	int* data;
	int capacity;
	int size;
};
maxheap create(void){
	maxheap ret=(maxheap)malloc(sizeof(struct heapstruct));
	ret->capacity=maxsize;
	ret->data=(int*)malloc(sizeof(int)*(ret->capacity+1));
	
	ret->size=0;
	ret->data[0]=hugenum;
	return ret;
}
maxheap insert(maxheap h,int x){
	if(h->size==h->capacity){
		printf("堆满!\n");
	}else{
		h->data[++h->size]=x;
		int child=h->size;
		int parent=child/2;
		while(h->data[child]>h->data[parent]){
			int temp=h->data[child];
			h->data[child]=h->data[parent];
			h->data[parent]=temp;
			child=parent;
			parent=child/2;
		}
	}
	return h;
}
int del(maxheap h){
	int ret;
	if(h->size){	
		ret=h->data[1];
		h->data[1]=h->data[h->size];
		h->size--;
		int parent=1;
		int child=2*parent;
		for(;child<=h->size;){
			int max=h->data[child];//默认左子树最大
			int pos =child;
			if((child+1)<=h->size&&h->data[child+1]>h->data[child]){
				max=h->data[child+1];
				pos=child+1;
			} 
			if(h->data[parent]>=max){
				break;
			}else{
				int temp=h->data[parent];
				h->data[parent]=max;
				h->data[pos]=temp;
				parent=pos;
				child=2*parent;
			}
			
		}		
	}else{
		printf("堆空!"); 
	}	
	return ret;
}