堆是一种特殊的数据结构它不同与我们队列和栈堆属于二叉树的范畴另外堆分为大堆和小堆大堆简单理解为就是父节点大于等于它的子节点小堆就是父节点小于等于它的子节点大堆小堆都属于完全二叉树。为了便于访问各个节点这里使用数组实现堆。已知父节点是i那么左子树就是2i1柚子树就是2i2已知任意一个子树节点的下标是i那么它的父节点就是i-1/2这是因为整数的除法只保留整数位。一、创建堆的结构体typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap;这里的结构体内容同顺序表一样二、堆的初始化//堆的初始化 void HeapInit(Heap* php) { assert(php); php-_a NULL; php-_capacity 0; php-_size 0; }三、堆的销毁// 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); if (hp-_a NULL) { return; } free(hp-_a); hp-_capacity 0; hp-_size 0; }四、堆的插入//向上调整 void AdjustUp(HPDataType* arr,int size) { assert(arr); int sub size - 1;//取到数组最后一个节点的下标 int son sub; int father (son - 1) / 2;//找到它的父亲 while (son 0)//子节点下标是永远不为0的 { if (arr[son] arr[father])//如果子节点小于父亲那么进行交换 { HPDataType flag arr[son]; arr[son] arr[father]; arr[father] flag; son father;//交换完成父节点成为新的子节点即向上调整 father (son - 1) / 2;//向上更新父节点 } else//不满足更新条件退出函数 { return; } } } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); //判断是否需要扩容 if (hp-_capacity hp-_size) { int newcapacity (hp-_capacity 0) ? 4 : hp-_capacity * 2; HPDataType* newhp (HPDataType*)realloc(hp-_a, newcapacity * sizeof(HPDataType)); if (newhp NULL) { perror(realloc error!); return; } hp-_a newhp; hp-_capacity newcapacity; } //插入数据在叶子上 hp-_a[hp-_size] x; hp-_size; //向上调整 AdjustUp(hp-_a, hp-_size); }为了保持小堆的格式这里使用尾插并向上调整的算法这个算法中传入的形式参数是需要调整的数组和该数组有效元素个数具体逻辑请看注释。五、堆数据的删除//向下调整 //sub是调整的目标的下标目的是将较小的数据移到靠近根 void AdjustDown(HPDataType* arr, int size ,int sub) { //确保有左孩子满足最小的交换条件 while (sub * 2 1 size) { int secondson; int bigson; //确保有右孩子才能进行左右孩子的交换 if (sub * 2 2 size) { //假设左孩子小于右孩子 secondson 2 * sub 1; bigson secondson 1; //如果左孩子大于右孩子则交换左右孩子下标 if (arr[secondson] arr[bigson]) { int flag bigson; bigson secondson; secondson flag; } } else//没有右孩子那么小儿子就是左孩子 { secondson 2 * sub 1; } //开始向下调整 //如果父亲大于两个孩子之间最小的那一个那么久做一次交换 if (arr[secondson] arr[sub]) { HPDataType newdata arr[secondson]; arr[secondson] arr[sub]; arr[sub] newdata; sub secondson; } else//未满足交换条件退出函数 { return; } } } // 堆的删除 void HeapPop(Heap* hp) { assert(hp); assert(hp-_size); hp-_a[0] hp-_a[hp-_size - 1];//交换最后一个节点和第一个节点 hp-_size--;//删除节点原理同顺序表 //向下调整 AdjustDown(hp-_a, hp-_size,0); }因为删除没有插入那样简单直接删除掉根之后他下边的所有子节点便群龙无首因此我们不能直接删除根所以有大神使用将首尾位节点互换然后再向下调整根的数据的算法。因为互换的叶子节点肯定比互换前的根大所以需要向下调整互换后的根节点。至于为什么要比较左右节点的大小那是因为我们要把尽可能小的数据移动到尽可能靠近根的位置所以才需要比较左右节点的大小以满足小堆的格式。六、取堆顶的数据// 取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); return hp-_a[0]; }七、求堆的数据个数// 堆的数据个数 int HeapSize(Heap* hp) { return hp-_size;//返回数据个数 }八、堆的判空// 堆的判空 int HeapEmpty(Heap* hp) { return hp-_size 0;//判断堆的数据个数是否等于0如果是返回非0否返回0 }九、测试代码void test() { Heap HP; HeapInit(HP); for (int i 0; i 100; i)//随机生成100个数据并插入进堆 { HeapPush(HP, rand()%1000); } while (!HeapEmpty(HP))//按照顺序取出数据 { printf(%d , HeapTop(HP)); HeapPop(HP); } HeapDestory(HP); } int main() { test(); return 0; }十、测试结果满足小堆的结构。