堆的概念

堆总是一个完全二叉树。
大堆：树中一个树及子树中，任何一个父亲都大于等于孩子。
小堆：树中一个树及子树中，任何一个父亲都小于等于孩子。

大堆

我们可以看到 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，点击此处获取