数据结构：3.7 堆的操作集实现

//对象集：完全二叉树
//用数组存储


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


//创建容量为Maxsize的最大堆
MaxHeap Create ( int Maxsize ) {
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    H->Data = malloc( (Maxsize+1) * sizeof(ElementType) );
    H->size = 0;
    H->Capacity = Maxsize;
    H->Data[0] = MaxData;  //定义“哨兵”为大于堆中所有可能元素的值，便于之后操作
    
    return H;
}

//插入  (插入到最后并调整堆成合理)
void Insert ( MaxHeap H, ElementType item ) {
    int i;
    if ( IsFull(H) ) {
        printf("堆已满");
        return;
    }
    i = ++H->Size; // i指向插入后堆中最后一个元素的位置
    for ( ; H->Data[i/2] < item; i/=2 )
        H->Data[i] = H->Data[i/2];    //item默认插入到i的位置，并与父结点逐个比较过滤
    H->Data[i] = item;   //插入
}

//删除   (取出根结点，同时删除一个结点)
ElementType DeleteMax ( MaxHeap H ) {
    int Parent, Child;
    ElementType MaxItem, temp;
    if ( IsEmpty(H) ) {
        printf("最大堆已空");
        return;
    }
    MaxItem = H->Data[1];  //取出根结点最大值
    //用最大堆中最后一个元素补充根，然后从根结点开始过滤下层
    temp = H->Data[H->Size--];
    for ( Parent=1; Parent*2 <= H->Size; Parent=Child ) {
        Child = Parent*2;
        if ( (Child!= H->Size) && (H->Data[Child] < H->Data[Child+1]) )
            Child++;  //Child指向左右子结点的较大者
        if ( temp >= H->Data[Child] ) break;
        else 
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = temp;
    return MaxItem;
}