堆的概念
堆：堆通常是一个可以被看一颗完全二叉树的数组对象
而堆又可以分成俩种：大堆：左右孩子（子树）都比父亲大的完全二叉树
小堆：左右孩子（子树）都比父亲小的完全二叉树
#大堆：
我们以一组数来举例：75 56 46 45 32
小堆：
堆的结构声明
堆的底层结构实际上是一个动态的
顺序表
typedef int Datatype;
typedef struct Heap
{
Datatype* a;
int size; //记录当前元素个数
int capacity; //记录容量大小
}Hp;
堆的初始化
就是将a初始化为空指针，然后将size和capacity
//初始化函数
void InitHeap(Hp* hp)
{
assert(hp);
//hp = (Hp*)malloc(sizeof(Hp)); //错误的
hp->a = NULL;
hp->capacity = hp->size = 0;
}
堆的销毁
就是将a在动态区的管理的空间释放掉，然后将size和capacity归0
//销毁函数
void DestroyHeap(Hp* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
插入数据
由于我们一开始是没有为a开辟好
动态内存空间
的，所以我们在进行增容的时候要处理第一次插入数据时的内存开辟:
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
而我们发现:将一个数插入进去时，是还没形成堆结构的。
如果我们要实现堆，就要保证树中的父亲要大于或者小于他的俩个孩子，所以我们每次插入时都需要进行数据位置的调整。
下面我们以构建大堆来举例：
还是拿原来的数据：75 56 46 45 32
假设我们现在要插入一个100到堆里面：
初始状态如下：
我们发现对于父亲46来说 是比100要小的 不满足我们大堆的定义
所以我们要做出调整 怎么调整呢？ 根据定义出发（左右孩子都比父亲要小）
只要将比父亲大的孩子与父亲的位置进行调整
先将100和其父亲46的位置进行调整， 然后我们会再次发现100还是会比他的新父亲（75）要大的，所以我们还要再次做出调整 将75和100互换
这里寻找的父亲坐标是有公式的：
p
a
r
e
n
t
=
(
c
h
i
l
d
−
1
)
/
2
parent=(child-1)/2
p
a
r
e
n
t
=
(
c
h
i
l
d
−
1
)
/
2
L
e
f
t
c
h
i
l
d
=
2
∗
p
a
r
e
n
t
+
1
Leftchild=2*parent+1
L
e
f
t
c
h
i
l
d
=
2
∗
p
a
r
e
n
t
+
1
R
i
g
h
t
c
h
i
l
d
=
2
∗
p
a
r
e
n
t
+
2
Rightchild=2*parent+2
R
i
g
h
t
c
h
i
l
d
=
2
∗
p
a
r
e
n
t
+
2
例子：比如说我们现在要找46的父亲下标 即（2-1）/2=0 就求出46的父亲的下标为0
或者是56左右孩子的下标 由公式 左孩子的下标：1乘2+1=3 ，右孩子的下标：1乘2+2=4
调整的方法为：将新插入的数据下标赋给child ，然后再求出父亲的下标parent ，将俩个位置的值进行比较，如果a[child]>a[parent],就将俩个位置的值互换，然后将parent再次赋给child,再利用新的child求出新的parent ,继续与新的父亲进行比较，如此迭代下去，然后此调整的出口有俩个：
1.当child走到祖先节点时
2.当a[child]不再大于a[parent]
//向上调整函数
void AdjustUp(Datatype * tree ,int Child)
{
assert(tree);
int parent = (Child - 1) / 2;//得到父节点的下标
//(parent >=0 ) //此处不好的原因是 child=0的时 即走到堆顶了 parent=0 还会进去循环 从else 出去
while(Child>0)
{
//大堆
if ( tree[Child] >tree[parent] )
{
/*Datatype tmp = tree[parent];
tree[parent] = tree[Child];
tree[Child] = tmp;*/
Swap( &tree[Child], &tree[parent] );
//迭代往上走
Child = parent;
parent = (Child - 1) / 2;
}
else
{
break;
}
}
}
void PushHeap(Hp* hp, Datatype x)
{
assert(hp);
//先检测容量
if (hp->capacity == hp->size)
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
Datatype* tmp = (Datatype*)realloc(hp->a, sizeof(Datatype) * newcapacity );
hp->capacity = newcapacity;
hp->a = tmp;
}
//插入数据
hp->a[hp->size] = x;
++hp->size;
//调整堆
AdjustUp(hp->a,hp->size-1);
}
删除数据
堆的删除数据的定义和其他数据结构不同，堆删除数据是从堆顶进行删除的
如果我们直接删除堆顶元素的话，然后将数组整体往前挪的，就会出现以下状况，直接全部乱套了
所以我们发现这种方式是不可取的。
下面我们给出思路
- 将堆顶位置的数据和堆尾位置的数据互换
- 将堆尾数据删除
- 进行向下调整： 向下调整主要看我们构建的是小堆还是大堆（大小堆取决我们向上与向下调整时的比较符号），就拿我们当前大堆来举例，我们每次进行向下调整都选择左右孩子中较大的孩子，当我们的父亲节点46不再小于俩个子节点或者已经走到了叶子节点时，调整就结束了
动图演示如下:
//弹出堆顶元素
void PopHeap(Hp* hp)
{
assert(hp);
//交换堆顶元素和堆底元素
Swap( &hp->a[0], &hp->a[hp->size - 1]);
//去除堆底元素
--hp->size;
//向下调整
Adjustdown(hp->a,hp->size,0);
}
//向下调整 //俩个出口 一个是当子节点遍历到叶节点时 二：当父节点不大于或者小与子节点时
void Adjustdown(Datatype * tree,int n,int parent)
{
int child = parent * 2 + 1;//默认较小或者较大的子节点为左孩子
while (child < n)
{
if ( (child+1)<n && tree[child +1] > tree[child] )
{
child++;//更换成右节点
}
if (tree[child] > tree[parent])
{
Swap( &tree[child], &tree[parent] );
//往下迭代
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
堆的其他接口
//获取堆的元素大小
int Heapsize(Hp* hp)
{
assert(hp);
return hp->size;
}
//获取堆的容量大小
int HeapCapacity(Hp* hp)
{
assert(hp);
return hp->capacity;
}
//获取堆顶元素
Datatype HeapTop(Hp* hp)
{
assert(hp);
assert(!emptyHeap(hp) ) ;
return hp->a[0];
}
感谢大佬们的支持，欢迎讨论与学习。