堆的基本操作

#pragma once
#include"stdio.h"
#include"stdlib.h"
#include"assert.h"
#include"stdbool.h"
typedef int HPDataType;
typedef struct Heap{
    HPDataType *a;
    int size;
    int capacity;
}HP;
void Swap(HPDataType*ps,HPDataType*py);   //交换避免冗余
void HeapInit(HP*hp);                     //初始化
void HeapDestroy(HP*hp);                  //销毁
void HeapPush(HP*hp,HPDataType X);        //插入X
void HeapPop(HP*hp);                      //删除
void HeapPrint(HP*hp);                    //打印
bool HeapEmpty(HP*hp);                    //检测是否为空
int HeapSize(HP*hp);                      //看有多少个

//初始化
void HeapInit(HP*hp){                        
    assert(hp);
    hp->a=NULL;
    hp->size=hp->capacity=0;
}
//销毁
void HeapDestroy(HP*hp){
    assert(hp);
    free(hp->a);
    hp->capacity=hp->size=0;
}

void AdjustUp(int *a,int child){            //向上调整下面还是详解，注意的是他这个实际本质还是拿数组存
    assert(a);
    int parent=(child-1)/2;
    while(child>0){
        if(a[child]>a[parent]){
            Swap(&a[child],&a[parent]);
            child=parent;
            parent=(child-1)/2;
        }
        else break;
    }
}
void HeapPush(HP*hp,HPDataType x){             //HeapPush要求，插入一个X保证原有的堆，原来大堆插入后还得是大堆
    assert(hp);
    if(hp->size==hp->capacity){
        size_t newCapacity=hp->capacity==0?4:hp->capacity*2;  //由于开始时capacity有可能是0
        HPDataType*tmp=realloc(hp->a,sizeof(HPDataType)*newCapacity);//后面放realloc用法的细节
        if(tmp==NULL){
            printf("realloc fail\n");
            exit(-1);
        }
        hp->a=tmp;
        hp->capacity=newCapacity;
    }
    hp->a[hp->size]=x;
    hp->size++;
    AdjustUp(hp->a,hp->size-1);
}

int HeapSize(HP*hp){
    assert(hp);
    return hp->size;
}

bool HeapEmpty(HP*hp){
    assert(hp);
    return hp->size==0;
}

void AdjustDown(int *a,int n,int parent){
    int child=parent*2+1;
    while(child<n){         //左孩子是否到了叶节点也就是底
        //选择左右孩子哪个才是最小的
        if(child+1<n&&a[child+1]<a[child]){           //child+1是右孩子，右孩子可能不存在，所以也要判断一下。
            ++child;
        }
  //如果最小的孩子小于父亲，交换，并且接着向下面调整，否则推出
        if(a[child]<a[parent]){
            Swap(&a[child],&a[parent]);            //换值
            parent=child;                          //换下标
            child=parent*2+1;
        }
        else{
            break;
        }
    }
}
//删除堆顶数据（删除树的根,也就是找最值）
void HeapPop(HP*hp){
    assert(hp); 
    assert(!HeapEmpty(hp));                        //看hp有没有值是不是空
    Swap(&hp->a[0],&hp->a[hp->size-1]);            //堆顶和最后的交换位置
    hp->size--;                                    //删除堆顶
    AdjustDown(hp->a,hp->size,0);
}