堆（Heap）

浙大数据结构
堆（Heap）
最大堆（MaxHeap）和最小堆（MinHeap）

结构性：用数组表示 完全二叉树
有序性：
任一结点的关键字是其子树所有结点的最大值（或最小值）
从根结点到任意结点路径上结点序列的有序性

#include 
#include 
 
using namespace std;

typedef int ElementType;

typedef struct HeapStruct{
	ElementType *Elements;//存储堆元素的数组 
	int Size;//堆的当前元素个数 
	int Capacity;//堆的最大容量 
}MaxHeap;


MaxHeap *Create(int MaxSize){
	MaxHeap *H = (MaxHeap *)malloc(sizeof(MaxHeap));
	H->Elements = (ElementType *)malloc((MaxSize+1) * sizeof(ElementType));
	H->Size = 0;
	H->Capacity = MaxSize;
	//H->Elements[0] = MaxData;  定义哨兵为大于堆中所有可能元素的值 
	return H; 
}


int IsFull(MaxHeap *H){
	return (H->Size == H->Capacity);
} 

 
void Insert(MaxHeap *H, ElementType item){
	int i;
	if(IsFull(H)){
		cout << "最大堆已满！" << endl;
		return ; 
	}
	i = ++H->Size;
	 
	//H->Elements[0] = item; 
	for(i; i>1 && H->Elements[i/2]Elements[i] = H->Elements[i/2];//向下过滤结点 
	}
	H->Elements[i] = item;//将item插入 
} 

int IsEmpty(MaxHeap *H){
	return (H->Size == 0);
} 

ElementType DeleteMax(MaxHeap *H){
	
	int Parent, Child;
	ElementType MaxItem, temp;
	if(IsEmpty(H)){
		cout << "最大堆已空！" << endl;
		return NULL; 
	}
	MaxItem = H->Elements[1];
	temp = H->Elements[H->Size--];
	for(Parent=1; Parent*2<=H->Size; Parent=Child){//Parent=Child 移动到下一层 
		 
		Child = Parent * 2;//一个完全二叉树的数组存储  父亲的两倍是左儿子 +1是右儿子 
		if((Child!=H->Size) && (H->Elements[Child]Elements[Child+1])){
			Child++;//Child指向左右子结点的较大者 
		}
		if(temp >= H->Elements[Child]){
			break;//比较大的儿子还要大，就返回他的父亲下标 Parent 
		}else{//否侧就用较大儿子代替父亲 
			H->Elements[Parent] = H->Elements[Child];
		}
	}
	H->Elements[Parent] = temp; 
	return MaxItem;
} 
 

 
int main(){
	MaxHeap *H;
	int MaxSize = 10; 
	H = Create(MaxSize);
	 
	if(IsEmpty(H)) cout << "堆空！" << endl;
	
	for(int i=0; i> item;
		Insert(H, item); 
		if(IsFull(H)) cout << "堆满！" << endl;
	}
	
	for(int i=0; i