数据结构——堆

堆

什么是堆

把所有的元素按照完全二叉树的形式储存在一维数组中，如果该二叉树满足父节点小于等于子节点，叫做小堆；如果该二叉树满足父节点大于等于子节点，叫做大堆。

堆的实现

堆类型的创建

堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。
堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数。

typedefint HPDataType;typedefstructheap{
    HPDataType* arr;int size;int capacity;}Heap;

堆的初始化

voidHeapInit(Heap* hp){assert(hp);
    hp->arr =NULL;
    hp->size = hp->capacity =0;}

堆的向上调整算法和向下调整算法

向上调整算法

给我的节点当做子节点，然后找到父节点，比较父子的大小，（看你是想建小堆还是大堆），直到比到子节点到根节点就停止比较，这时就已经调整好一次了。
下面的这个例子调整成的是小堆

voidswap(HPDataType* a, HPDataType* b){
    HPDataType c =*a;*a =*b;*b = c;}voidadjustup(Heap* hp,int child){int father =(child -1)/2;while(child >0){if(hp->arr[child]< hp->arr[father]){swap(&(hp->arr[child]),&(hp->arr[father]));
            child = father;
            father =(child -1)/2;}elsebreak;}}

向下调整算法

给我的节点当做父节点，然后找到子节点(这个节点为左孩子，我们需要找到这两个孩子中较大的或者较小的当作子节点)，比较父子的大小，（看你是想建小堆还是大堆），直到比到子节点超过节点个数的时候就停止比较，这时就已经调整好一次了。

voidadjustdown(Heap* hp,int father){int child =2* father +1;while(child < hp->size){//因为这里有child+1，所以要注意边界问题if(child < hp->size-1&&hp->arr[child]> hp->arr[child +1])
            child++;if(hp->arr[child]< hp->arr[father]){swap(&(hp->arr[child]),&(hp->arr[father]));
            father=child;
            child =2* father +1;}elsebreak;}}

堆的插入

为了不破坏堆的性质，我们在堆的最后进行插入(想一下其实在最后进行插入就不需要调整其他的元素了)
插入完成之后，我们需要调整成堆的形式。这里我们用堆的向上调整算法。进行调整.

voidHeapPush(Heap* hp, HPDataType x){assert(hp);if(hp->size == hp->capacity){int newcapcity = hp->capacity ==0?4: hp->capacity *2;
        HPDataType* newarr =(HPDataType*)realloc(hp->arr, newcapcity *sizeof(HPDateType));if(newarr ==NULL)exit(-1);
        hp->arr = newarr;
        hp->capacity = newcapcity;}
    hp->arr[hp->size]= x;
    hp->size++;//向上调整adjustup(hp,hp->size-1);}

堆的删除

对于删除堆头的数据，我们是把堆尾的数据覆盖头，元素个数减1，然后用堆的向下调整算法，进一步调整成堆。

voidHeapPop(Heap* hp){assert(hp);assert(hp->size);swap(&(hp->arr[0]),&(hp->arr[hp->size-1]));
    hp->size--;//向下调整adjustdown(hp,0);}

堆的销毁

voidHeapDestrop(Heap* hp){assert(hp);free(hp->arr);
    hp->size = hp->capacity =0;}

打印堆

voidHeapPrint(Heap* hp){assert(hp);for(int i =0; i < hp->size; i++){printf("%d ", hp->arr[i]);}printf("\n");}