C语言|C语言深入解读数据结构之堆的实现 C语言深入解读数据结构之堆的

堆的概念与结构概念：如果有一个关键码的集合K={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足K i<=K 2*i+1且Ki<=K 2*i+2(K i>=K 2*i+1且Ki>=K 2*i+2) i = 0，1，2...，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

结构：
1.大堆

文章图片

2.小堆

文章图片

堆(大根堆)的实现：堆的接口：

#pragma once#include#include#include#includetypedef int HPDataType; typedef struct Heap{HPDataType* a; int size; int capacity; }HP; //堆的创建void HeapInit(HP*hp); //堆的销毁void HeapDestroy(HP*hp); //交换数值void Swap(HPDataType *px, HPDataType *py); //向上调整void AdjustUp(int *a,int child); //向下调整void AdjustDown(int *a, int n, int parent); //堆的插入void HeapPush(HP*hp,HPDataType x); //堆的删除void HeapPop(HP*hp); //取堆顶的数据HPDataType HeapTop(HP*hp); //打印堆void HeapPrint(HP*hp); //堆的判空bool HeapEmpty(HP*hp); //堆的数据个数int HeapSize(HP*hp);

堆的创建：

void HeapInit(HP*hp){assert(hp); hp->a=NULL; hp->capacity=hp->size=0; }

堆的销毁：

void HeapDestroy(HP*hp){assert(hp); free(hp->a); hp->capacity=hp->size=0; }

交换数值：

void Swap(HPDataType*px, HPDataType*py){HPDataType tmp = *px; *px=*py; *py=tmp; }

向上调整：

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){assert(hp); if(hp->capacity==hp->size){size_t newCapacity=hp->capacity==0?4:hp->capacity*2; HPDataType * tmp=(HPDataType*)realloc(hp->a,newCapacity*sizeof(HPDataType)); if(tmp==NULL){printf("realloc is fail\n"); }hp->a=tmp; hp->capacity=newCapacity; }hp->a[hp->size-1]=x; hp->size++; //向上调整AdjusiUp(hp->a,hp->size-1); }

【C语言|C语言深入解读数据结构之堆的实现】向下调整：

void AdjustDown(int *a,int n,int parent){int child=parent*2+1; while(childa[child]){child++; }if(a[child]>a[parent]){Swap(&a[child],&a[parent]); parent=child; child=parent*2+1; }else{break; }}}

堆的判空：

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

堆的删除：

void HeapPop(HP*hp){ assert(hp); //堆的判空 assert(!HeapEmpty(hp)); //交换数值 Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; //向下调整 AdjustDown(hp->a, hp->size, 0); }

取堆顶的数据：