注：这里我们所实现的是大根堆（即父节点不小于子节点的堆）
目录
一，堆的介绍
二，堆结构的创建
三，接口实现
1，初始化与销毁
2，数据的插入与删除
3，其他接口
一，堆的介绍
两种结构：
在物理结构上，堆就是一块连续的储存空间，对应数组
在逻辑结构上，堆是一棵完全二叉树
两种形式：
大根堆：父节点不小于子节点
小根堆：父节点不大于子节点
二，堆结构的创建
三个成员，指向数组的指针datas，表示数组中有效数据个数的size，表示数组容量的capacity
typedef int HeapDataType;
typedef struct Heap
{
HeapDataType* datas;
int size;
int capacity;
}Heap;
这里如果我们对比堆和顺序表，可以发现结构体的创建可以说是一摸一样的，我想这就体现出了数据结构的精髓在于思想的这点，同一个结构体因为使用方式的不同，从而使它发挥出了不同作用，变成了新的模样。
三，接口实现
1，初始化与销毁
初始化，在使用堆之前，置空堆的成员；
销毁，在使用堆之后，释放空间，置空堆的成员；
void HeapInit(Heap* pHeap);
void HeapInit(Heap* pHeap)
{
assert(pHeap != NULL);
pHeap->datas = NULL;
pHeap->size = pHeap->capacity = 0;
}
void HeapDestroy(Heap* pHeap);
void HeapDestroy(Heap* pHeap)
{
assert(pHeap != NULL);
free(pHeap->datas);
pHeap->datas = NULL;
pHeap->size = pHeap->capacity = 0;
}
2，数据的插入与删除
void HeapPush(Heap* pHeap, HeapDataType x);
数据插入前首先检查容量是否足够，不够则需要扩容，空间足够后插入数据，但这时数据的结构可能不满足堆的要求了（大根堆要求父节点不小于子节点，新节点可能不满足这种关系），此时需要调整（这里的调整称为向上调整）
void HeapPush(Heap* pHeap, HeapDataType x)
{
assert(pHeap != NULL);
HeapCheckCapacity(pHeap);
pHeap->datas[pHeap->size] = x;
AdjustUp(pHeap->datas, pHeap->size);
pHeap->size++;
}
向上调整的做法是首先找到新节点的父节点，通过比较大小来判断是否进行数据的交换（子节点大于父节点则交换，反之不需调整），如果进行了交换还需要继续判断，直到新数据到了合适的位置（满足堆的要求）
void AdjustUp(HeapDataType* datas, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (datas[child] > datas[parent])
{
Swap(&datas[child], &datas[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void Swap(HeapDataType* x, HeapDataType* y)
{
HeapDataType temp = *x;
*x = *y;
*y = temp;
}
void HeapCheckCapacity(Heap* pHeap)
{
if (pHeap->size == pHeap->capacity)
{
int newcapacity = 2 * pHeap->capacity;
pHeap->datas = (HeapDataType*)realloc(pHeap->datas, sizeof(HeapDataType) * newcapacity);
assert(pHeap->datas != NULL);
pHeap->capacity = newcapacity;
}
}
void HeapPop(Heap* pHeap);
注意这里的删除操作，删除的是根节点
堆根节点的删除，首先交换数组首元素和尾元素的数据，然后进行调整（首尾元素数据交换后数据的结构可能不满足堆的要求），这里的调整称为向下调整
void HeapPop(Heap* pHeap)
{
assert(pHeap != NULL);
assert(HeapEmpty(pHeap) != true);
Swap(&(pHeap->datas[0]), &(pHeap->datas[pHeap->size - 1]));
pHeap->size--;
AdjustDown(pHeap->datas, pHeap->size, 0);
}
与向上调整相似，向下调整的做法是首先找到根节点的子节点（较大的子节点），通过比较大小来判断是否进行数据的交换（子节点大于父节点则交换，反之不需调整），如果进行了交换还需要继续判断，知道根数据到了合适的位置（满足堆的要求）
void Swap(HeapDataType* x, HeapDataType* y)
{
HeapDataType temp = *x;
*x = *y;
*y = temp;
}
void AdjustDown(HeapDataType* datas, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && datas[child] < datas[child + 1])
{
child += 1;
}
if (datas[parent] < datas[child])
{
Swap(&datas[parent], &datas[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
3，其他接口
HeapDataType HeapTop(Heap* pHeap);查看根节点数据
HeapDataType HeapTop(Heap* pHeap)
{
return pHeap->datas[pHeap->size - 1];
}
bool HeapEmpty(Heap* pHeap);判断堆是否为空
bool HeapEmpty(Heap* pHeap)
{
return pHeap->size == 0 ? true : false;
}
int HeapSize(Heap* pHeap);查看堆有效数据的多少
int HeapSize(Heap* pHeap)
{
return pHeap->size;
}
