堆的删除（最大堆）
思路
代码
ElementType DeleteMax( MaxHeap H ) { /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */ int Parent, Child; ElementType MaxItem, X; if ( IsEmpty(H) ) { printf("最大堆已为空"); return ERROR; } MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */ /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */ X = 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( X >= H->Data[Child] ) { break; /* 找到了合适位置 */ } else /* 下滤X */ { H->Data[Parent] = H->Data[Child]; } } H->Data[Parent] = X; return MaxItem; }
解析
判断最大堆是否为空，如果为空则返回错误。
取出根结点存放的最大值，即最大元素。 放在临时变量MaxItem中。
将堆的规模减一。
这里的变量parent，用于表示当前结点的父结点在最大堆中的下标位置。
在删除最大值的操作中，我们需要将最后一个元素放到根结点的位置，
然后从根结点开始向下过滤，找到合适的位置，使得最大堆的性质得以保持。
在向下过滤的过程中，我们需要比较当前结点和其左右子结点的大小关系，
如果当前结点比其子结点都大，那么就找到了合适的位置，可以结束操作。
否则，我们需要将当前结点和其子结点中较大的那个交换位置，然后继续向下过滤。
在这个过程中，parent变量的作用是表示当前结点的下标位置，方便我们进行比较和交换操作。
在最大堆中，每个结点的左子结点下标为2i，右子结点下标为2i+1，其中i为当前结点的下标。
当一个结点只有左子结点时，其右子结点下标为2i+1，超出了最大堆的范围，
因此需要判断 child != H->size，即该节点是否有右子节点，（child先指向的是左子结点，若child == H->size，就说明已经是堆中的最大值了，意味着没有右子结点了）
如果有，则需要比较左右子节点的大小，选择较大的子节点进行下滤操作。
如果没有右子节点，则直接将左子节点与X进行比较。
最后，将 X 插入到 Parent 的位置上即可。
函数结束，返回最大堆中键值最大的元素。
end
