编辑代码

#include <stdio.h>
#include <malloc.h>

#define MaxData 1000

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

MaxHeap Create(int MaxSize);
void Insert(MaxHeap H,int item);
int DeleteMax(MaxHeap H);
int IsEmpty(MaxHeap H);
int IsFull(MaxHeap H);

int IsFull(MaxHeap H){
    if(H->Size == H->Capacity){
        return 1;
    }else{
        return 0;
    }
}

int IsEmpty(MaxHeap H){
    if(H->Size == 0){
        return 1;
    }else{
        return 0;
    }
}

//从最大堆H中取出键值为最大的元素，并删除一个结点
int DeleteMax(MaxHeap H){
    int MaxItem,temp,parent,child;
    if(IsEmpty(H)){
        printf("堆为空");
        return 0;
    }
    //取出根节点最大值
    MaxItem = H->Elements[1];
    //用最大堆中最后一个元素从根结点开始向上过滤下层结点
    temp = H->Elements[H->Size--];
    /*找到temp的位置，从而保证最大堆的有序结构
      parent*2 < Size：
        这个条件用于判断是否存在
        左孩子，有左孩子时才进入循环，若大于Size，
        则无左孩子，更无右孩子
      child：当有左右孩子时，child用于指向其中的
        较大值
    */
    for(parent = 1;parent*2 < H->Size;parent = child){
       child = parent * 2;
       /*child != Size:
            这个条件用于判断右孩子是否存在，当child等于Size时，
            不存在右孩子，因为child为左孩子，它为最后一个元素，
            所以等于的话肯定没有右孩子，不等于才能比较左右孩子
            的大小
       */
       if( (child != H->Size) && (H->Elements[child] < H->Elements[child+1]) ){
           //child指向左右子结点的较大者
           child++;
       }
       //为最大了，直接跳出
       if( temp >= H->Elements[child]){
           break;
       }
       //否则，移动temp元素到下一层
       else{
           H->Elements[parent] = H->Elements[child];
       }
    }
    //找到了temp的最终位置
    H->Elements[parent] = temp;
    //返回删除的堆顶的元素的值
    return MaxItem;
}

void Insert(MaxHeap H,int item){
    int i;
    if(IsFull(H)){
        printf("最大堆已满");
        return;
    }
    //i指向插入后堆中的最后一个元素的位置，当前要放进去的位置
    //i = ++H->Size;
    for(i = ++H->Size;H->Elements[i/2] < item;i/=2){
        /*父结点比item要小，向下过滤结点，父结点挪下来（循环）
          主要是拿到每一个父结点的值与item判断，从而确定要插
          入的位置，故如果父结点小于item的话就向下赋值
          （错误的理解：不是插入之后再比较，所以不用交换新
            结点与父结点的值）
        */
        H->Elements[i] = H->Elements[i/2];
    }
        /*父结点比item要大，不再调整，将item插入
          H->Elements[0]是哨兵元素，它不小于堆中的
          最大元素，控制循环结束
        */
        H->Elements[i] = item;
}

//创建容量为MaxSize的空的最大堆
MaxHeap Create(int MaxSize){
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    /*Elements要指向一个数组，数组的大小为堆的容量+1
      +1：存放是从下标为1的位置开始存放的
    */
    H->Elements = malloc( (MaxSize + 1) * sizeof(struct HeapStruct));
    H->Size = 0;
    H->Capacity = MaxSize;
    /*
      定义“哨兵”，大于堆中所有元素的值
      这样做可以在判断有序性时，省去下标元素要大于1的判断（i>1）
      因为会一直与其父结点进行比较，就可能会比较到Elements[0]
    */
    H->Elements[0] = MaxData;
    return H;
}

int main () {
    int MaxSize,x,i,result;
    MaxHeap heap;
    scanf("%d",&MaxSize);
    //初始化堆
    heap = Create(MaxSize);
    for(i = 0;i < MaxSize;i++){
        printf("输入第%d个数据：\n",i);
        scanf("%d",&x);
        Insert(heap,x);
    }
    printf("最大堆为:\n");
    for(i = 1;i <= MaxSize;i++){
        printf("%d\n",heap->Elements[i]);
    }
    result = DeleteMax(heap);
    printf("删除堆顶的元素为：%d\n",result);
    printf("\n");
    printf("删除堆顶元素之后的堆为：\n");
    for(i = 1;i < MaxSize;i++){
        printf("%d\n",heap->Elements[i]);
    }
}