一. 堆的接口函数（续）
虽然我们的上一篇博客已经写过了堆的前面一些接口函数
这里我们再重复一遍
1. 结构体形式
我们这里形式上使用一个数组来表示一个逻辑上的二叉树
typedef int HPDateType; typedef struct Heap { HPDateType* a; int size; int capacity; }HP;
2. 初始化和销毁
这里的两个接口函数都很简单 我们直接连起来动手实现一下
初始化
void HeapInit(HP* php) { assert(php); php->a = (HPDateType*)malloc(sizeof(HPDateType) * 4); if (php->a == NULL) { perror("malloc fail"); return; } php->size =0; php->capacity = 4; }
销毁
void HeapDestroy(HP* php) { assert(php); free(php->a); php = NULL; php->size = 0; php->capacity = 0; }
3. 添加数据（小堆为例）
当我们这里插入一个10的时候 这里明显是错误的啊 怎么办呢？
这个时候我们就需要将它跟它的父亲比较 是否小于它的父亲
如果不小于就填入
如果大于就交换它和它的父亲
知道孩子等于0为止
下面开始写代码
void HeapPush(HP* php, HPDateType x) { assert(php); if (php->size == php->capacity) { HPDateType* tmp = (HPDateType*)realloc(php->a,sizeof(HPDateType) * php->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } php->a = tmp; php->capacity *= 2; } php->a[php->size] = x; php->size++; AdJustUp(php->a, php->size - 1); }
这里因为判断是否需要调整这个函数要使用很多次
所以说我们单独写出一个函数出来
void Swap(HPDateType* p1, HPDateType* p2) { HPDateType x = *p1; *p1 = *p2; *p2 = x; } //除child这个位置，前面数据构成堆 //向上调整 void AdJustUp(HPDateType* a, int child) { 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; } } }
整体代码如下
1. vovoid Swap(HPDateType* p1, HPDateType* p2) { HPDateType x = *p1; *p1 = *p2; *p2 = x; } //除child这个位置，前面数据构成堆 //向上调整 void AdJustUp(HPDateType* a, int child) { 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* php, HPDateType x) { assert(php); if (php->size == php->capacity) { HPDateType* tmp = (HPDateType*)realloc(php->a,sizeof(HPDateType) * php->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } php->a = tmp; php->capacity *= 2; } php->a[php->size] = x; php->size++; AdJustUp(php->a, php->size - 1); }
4. 删除数据
我们想要删除堆中的一个数据 还要不改变这个堆的结构 这个时候怎么办呢
这个时候我们这里给出一种很巧妙的解法
我们先将最前面的元素和最后面的元素交换位置
然后再删除掉堆最后面的元素
之后开始向下调整这个堆
如上图所示
下面是删除数据的大体逻辑
void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(&php)); //删除数据 Swap(&php->a[0], &php->a[php->size - 1]); php->size--;
这里我们还需要再写一个函数向下调整
void AdJustDown(HPDateType* a, int n, int parent) { int child = parent * 2 + 1; while(child < n) { //选出左右孩子中大的那一个 //需要先判断右孩子是否存在防止出现越界问题 if (child + 1<n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; //更新孩子的位置 child = parent * 2 + 1; } else { break; } } }
调整函数如上
我们再来整体看看这个函数
void AdJustDown(HPDateType* a, int n, int parent) { int child = parent * 2 + 1; while(child < n) { //选出左右孩子中大的那一个 //需要先判断右孩子是否存在防止出现越界问题 if (child + 1<n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; //更新孩子的位置 child = parent * 2 + 1; } else { break; } } } void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(&php)); //删除数据 Swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdJustDown(php->a, php->size, 0); }
测试一下试试
5. 返回大小
这个很简单 返回size大小
int HeapSize(HP* php) { assert(php); return php->size; }
7. 判断为空
bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
8.返回堆顶数据
HPDateType HeapTop(HP* php) { assert(php); return php->a[0]; }
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
