目录
- 堆的概念
- 堆的结构声明
- 堆的初始化
- 插入数据
- 移除数据
- 打印
堆的概念
堆总是一个完全二叉树。
大堆:树中一个树及子树中,任何一个父亲都大于等于孩子。
小堆:树中一个树及子树中,任何一个父亲都小于等于孩子。
大堆
我们可以看到 75比 60 和 70 大, 60 比 55 和 40 大,也就是树中任何一个父亲都大于或等于孩子,所以这是一个大堆。
小堆
而任何一个父亲都小于或等于孩子,这就是小堆。那么接下来我们来实现一个大堆。
堆的结构声明
那么我们用什么结构来实现堆呢?用链表和数组都可以,但是数组比较方便查找,所以我们这里用数组来实现一个堆。
所以堆的结构类似于我们的顺序表。
typedef int HeapDataType;typedef struct Heap
{HeapDataType* data;size_t sz;size_t Cacpcity;
}HP;
堆的初始化
让data指向空,数组长度和容量置为0
void HeapInit(HP* hp)
{hp->data = NULL;hp->sz = hp->Cacpcity = 0;
}
插入数据
因为有大堆和小堆的区分,所以数据的插入也会有所差异。因此我们这里实现大堆,那么就要保证树中父亲必须大于等于孩子。
那么再插入的时候,我们必须让孩子和它的父亲比较。
如图我们可以发现, 40 和 45的下标为 3 , 4 ,它们父亲 60的下标为1。
那我们可以总结出一个公式,父亲的下标 = (孩子的下标-1) / 2。
比如 60的下标是 1 , 40的下标是 3 , 那么 (3-1)/2 = 1, 比如 55的下标是2, 75的下标是 0 , ( 2 - 1 ) / 2 = 0。
而我们插入的时候,必须要和父亲比较,在大堆的情况下,孩子是不可能比父亲大的。
比如我要在 55的下面插入一个 80
我们称这个过程为向上调整。
//检查容量
void CheckCacpcity(HP* hp)
{if (hp->Cacpcity == hp->sz){//扩容size_t newCacpcity = hp->Cacpcity == 0 ? 4 : 2 * hp->Cacpcity;//扩容HP* newhp = realloc(hp->data, sizeof(HeapDataType) * newCacpcity);if (newhp == NULL){printf("realloc fail\n");exit(-1);}hp->data = newhp;hp->Cacpcity = newCacpcity;}
}//向上调整
void AdjustUp(HP* hp, int child)
{//至少比较一次do{int parent = (child - 1) / 2;//如果父亲小于孩子if (hp->data[parent] < hp->data[child]){//交换HeapDataType tmp = hp->data[child];hp->data[child] = hp->data[parent];hp->data[parent] = tmp;//更新childchild = parent;}else{break;}} while (child > 0);}void HeapPush(HP* hp, HeapDataType x)
{assert(hp);//先判断容量是否够用CheckCacpcity(hp);//插入数据hp->data[hp->sz] = x;hp->sz++;//向上调整AdjustUp(hp, hp->sz - 1);
}
移除数据
因为完全二叉树最后一层必须是连续的,所以我们直接 移除最后一个数据即可。
void HeapPop(HP* hp)
{assert(hp);hp->sz--;
}
打印
为了方便观察,我们再打印一下。
void HeapPrint(HP* hp)
{for (int i = 0; i < hp->sz; i++)printf("%d ", hp->data[i]);printf("\n");
}
随后 我们再插入一个大于父亲的数据试试效果。我们插入一个77。
我们就会发现,77和75调换位置了。实际上变成了这样。
堆的实现我们就讲到这里了,堆只是二叉树的一个小部分,后续会给大家分享更多关于二叉树的知识,感谢大家支持。代码已上传至git,点击此处获取