堆的原理及其完全二叉树代码实现

优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是 依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
如何用一种数据结构来组织堆：完全二叉树，树根就是此时数据优先度最高的，随着数据的插入删除，优先度最高的树根也在动态变化。
完全二叉树的表示：一维数组，其中arr[0]为哨兵元素。

typedef struct HeapStruct *MaxHeap; 
struct HeapStruct {
	 ElementType *Elements; /* 存储堆元素的数组 */
	 int Size;
	int Capacity; 
};
MaxHeap Create( int MaxSize ) {
/* 创建容量为MaxSize的空的最大堆 */
	MaxHeap H = malloc( sizeof( struct HeapStruct ) ); 
	H->Elements = malloc( (MaxSize+1) * sizeof(ElementType)); 
	H->Size = 0;
	H->Capacity = MaxSize;
	H->Elements[0] = MaxData; 
	/* 定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 */
	return H; 
}
//最大堆的插入
void Insert( MaxHeap H, ElementType item ) { 
/* 将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵 */ 
	if ( IsFull(H) ) { 
		printf("最大堆已满");
		return;
	}
	H->Elements[++size] = item;
	int i;
	for(i=size;i>0;i/=2)//上滤交换数据
	{
		if(H->Elements[i]<H->Elements[i/2])break;
		else {
			int t=H->Elements[i];
			H->Elements[i]=H->Elements[i/2];
			H->Elements[i/2]=t;
		}
	}
}
//最大堆的插入(加强版)
void Insert( MaxHeap H, ElementType item ) { 
/* 将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵 */ 
	if ( IsFull(H) ) { 
		printf("最大堆已满");
		return;
	}
	int i=++H->size;
	//找到item应该存在的位置
	for(;H->Elements[i/2]<item;i/=2)
		H->Elements[i]=H->Elements[i/2];
	H->Elements[i]=item;
}
//最大堆的删除
ElementType DeleteMax( MaxHeap H ) {
 /* 从最大堆H中取出键值为最大的元素，并删除一个结点 ，再用最后一个结点放到该处*/ 
 	if ( IsEmpty(H) ) 
 	{ 
 		printf("最大堆已为空");
 		return;
	}
	int parent ,child,maxitem;
	maxitem =  	H->Elements[1];
	int X=H->Elements[H->size--];
	for(parent =1;parent*2<=H->size;parent= chlid )
	{
		child = parent * 2;
		if((child!= H->Size) && (H->Elements[child] < H->Elements[child+1]))
			child++;
		if(H->Elements[child]<X)break;
		else {
			H->Elements[parent]=H->Elements[child];
		}
	}
	H->Elements[parent]= X;
	return maxitem;
}
//最大堆的建立
void PercDown( MaxHeap H, int p )
 { /* 将H中以H->Data[p]为根的子堆调整为最大堆 */
        int parent,child,X;
        X = H->Elements[p];
        for(parent=1;parent*2<=H->size;parent=child)
        {
        	child = parent*2;
        	if((child!= H->Size) && (H->Elements[child] < H->Elements[child+1]))
			child++;
			if(H->Elements[child]<X)break;
			else {
				H->Elements[parent]=H->Elements[child];
			}
		}
		H->Elements[parent]= X;
        }
}
void BuildHeap( MaxHeap H )
{ /* 调整H->Data[]中的元素，使满足最大堆的有序性  */
    /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
    int i;    /* 从最后一个结点的父节点开始，到根结点1 */
    for( i = H->Size/2; i>0; i-- )
        PercDown( H, i );
}