C. 쌓 기 (hep) 를 실현 하 는 두 가지 방식

#include
#include
#define mindata				-10001
#define maxsize				1000
typedef int ElemType; 
typedef struct	{						//        ?
	ElemType	*Elems;
	int			 size;
	int			 capacity;	
}HeapStruct,*MinHeap;

void MinHeapCreate (int Maxsize,MinHeap &H)
{
	H->Elems =(ElemType *) malloc((maxsize+1)*sizeof(ElemType));
	H->size=0;
	H->capacity=maxsize;
	H->Elems[0]=mindata;
} 

void swap(MinHeap &H,int a,int b)
{
	int temp;
	temp = H->Elems[a];
	H->Elems[a] = H->Elems[b];
	 H->Elems[b]=temp;
}

void shiftdown(MinHeap &H,int i)
{
    int t,flag=0;//flag               
    while(i*2<=H->size&&flag==0)
    {	//            ，  t           
    	if(H->Elems[i]>H->Elems[2*i]){
    		t=i*2;
    	}else{
    		t=i;
    	}
		//       ，         
		if(i*2 + 1 <= H->size)
		{
			//          ，          t
			if(H->Elems[t]>H->Elems[i*2+1])
			 	t=i*2+1;
		}
		//            ，              
		if(t!=i)
		{
			swap(H,t,i);
			i=t;
		}else{
			flag=1;
		} 
    }
}

void BulidMinHeap(MinHeap &H) 
{
	int i;
	for(i=H->size/2;i>0;i--)
		shiftdown(H,i);
}

int compare(MinHeap &H1,int child,int parent )
{
	int flag=0;
		if(H1->Elems[child]Elems[parent])
			flag=1;	
	return flag;		
}

void MinHeapinsert(MinHeap &H1,int N)
{
	scanf("%d",&H1->Elems[1]);
	H1->size++;
	int i;
		for(i=2;iElems[i]);
		H1->size++;
		int j=i;
		while(j/2>0&&j!=1){
		if(compare(H1,j,j/2)==1)
			swap(H1,j,j/2);
			j=j/2;	
		}
		}		
}
void print(MinHeap &H,int M,int *xb)
{
	for(int i=0;i1)
		{
			printf("%d ",H->Elems[a]);
			a=a/2;
		}
		printf("%d
",H->Elems[1]);	
	}
}
void gettop(MinHeap &H)
{
	int top = H->Elems[1];
	H->Elems[1]=H->Elems[H->size];
	H->size--;
	BulidMinHeap(H);
	printf("%d
",top);
	for(int i=1;i<=H->size;i++)
	printf("%d ",H->Elems[i]);
}
main()
{
	printf("     
");
	int N,M;
	MinHeap H =(MinHeap) malloc (sizeof(HeapStruct));
	MinHeapCreate (maxsize,H);
	scanf("%d %d",&N,&M);
	getchar();
	for(int i=1;iElems[i]);
		H->size++;
	}		
	BulidMinHeap(H); 
	for(int i=1;i<=H->size;i++)
	printf("%d ",H->Elems[i]);
	putchar(10);
	int xb[maxsize];
	print(H,M,xb);
	
	printf("     
"); 
	MinHeap H1 =(MinHeap) malloc (sizeof(HeapStruct));
	MinHeapCreate (maxsize,H1);
	scanf("%d %d",&N,&M);
	MinHeapinsert(H1,N);
	for(int i=1;i<=H1->size;i++)
	printf("%d ",H1->Elems[i]);
	putchar(10);
	print(H1,M,xb);
	//      ，                   ，                
	gettop(H);
	
	return 0;	
}