最大堆创建

• 将MaxData换成MinData，同样适用于最小堆；

typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
    ElementType *Data;  	// 存储堆元素的数组
    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;
}

最大堆的插入

• 将新增结点插入到从其父结点到根结点的有序序列中;
• H->Element[0]是哨兵元素，它不小于堆中的最大元素，控制顺环结束；

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

bool Insert(MaxHeap H, ElementType X)
{   // 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵
    int i;
    
    if (IsFull(H)) {
        printf("最大堆已满");
        return false;
    }
    i = ++H->Size;  // i指向插入后堆中的最后一个元素的位置
    for (; H->Data[i/2] < X; i/=2)
        H->Data[i] = H->Data[i/2] ; // 向上调整结点的值，保证最大堆的有序性
    H->Data[i] = X; // 将X插入
    return true;
}

最大堆的删除

• 取出根结点（最大值）元素，同时删除堆的一个节点，同时还需保持堆的有序性和完全二叉树的结构特性；

ElementType DeleteMax(MaxHeap H)
{   // 从最大堆H中取出键值为最大的元素，并删除一个结点
    int Parent, Child;
    ElementType MaxItem, temp;
    if (IsEmpty(H)) {
        printf("最大堆已为空");
        return;
    }
    MaxItem = H->Elements[1];  // 取出根结点最大值
    // 用最大堆中最后一个元素从根结点开始向上过滤下层结点，保证最大堆的有序性
    temp = H->Elements[H->Size--];
    for (Parent=1; Parent*2<H->Size; Parent=Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Elements[Child] < H->Elements[Child+1]))
            Child++; // Child指向左右子结点的较大者
        if (temp >= H->Elements[Child]) break;
        else // 移动temp元素到下一层
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = temp;
    return MaxItem;
}

最大堆的建立

• 方法二

void PercDown(MaxHeap H, int p)
{   // 下滤：将H中以H->Data[p]为根的子堆调整为最大堆
    int Parent, Child;
    ElementType X;
    
    X = H->Data[p] // 取出根结点存放的值
    for (Parent = p; Parent*2<H->Size; Parent=Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child] < H->Data[Child+1]))
            Child++;   // Child指向左右子结点的较大者
        if (X >= H->Data[Child])
            break;  // 找到了合适位置
        else // 下滤X
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[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)
}