堆的概念及结构
堆的要求 堆必须满足完全二叉树 堆的分类 堆分为两种： 1.小堆：任何一个孩子大于父亲 2.大堆：任意一个孩子都小于父亲 堆的结构 堆的逻辑结构：二叉树 堆的物理结构：数组 堆的用处：堆排序、topk 堆的特点 大堆可以找到最大值，小堆可以找到最小值
堆的接口
堆的表示
堆的底层用的是顺序表，所以堆的表示和顺序表是一样的。
代码语言：javascript复制typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;堆的初始化
因为堆的底层是数组，所以初始化和顺序表一样，可以先给一定的空间，也可以不给，代码如下：
代码语言：javascript复制void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}在堆中插入数据
在堆中插入数据我们要注意，有以下几种情况： 如果所示：
我们要在这个大堆的最后插入一个数据，我们可以看出这个堆事一个大堆，当我们插入一个比3小的数据时，我们是不用调的，因为它满足大堆的要求（所有的孩子都比父亲小），当我们插入比3大的数据时，我们就应该把这个数据往上调，通过比较孩子和父亲的大小，然后交换两个数据从而达到了调整的方法，这种方法我们把它叫做向上调整算法。 根据文字描述，可以得出下面的代码：
代码语言：javascript复制void AdJustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
}
else
{
break;
}
child = parent;
parent = (parent - 1) / 2;
}
}上面用到的Swap函数如下：
代码语言：javascript复制void Swap(HPDataType* ps, HPDataType* pq)
{
HPDataType tmp = *ps;
*ps = *pq;
*pq = tmp;
}在插入数据时，必须先验证一下空间是否足够，如果空间不够，就要开辟新的空间
代码语言：javascript复制//假设实现的是小堆
void HPPush(HP* php, HPDataType x)
{
assert(php);
//扩容
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* newnode = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (newnode == NULL)
{
perror("realloc failn");
return;
}
php->a = newnode;
php->capacity = newcapacity;
}
//插入数据
php->a[php->size] = x;
php->size ;
AdJustUp(php->a, php->size - 1);
}取出堆顶的数据
代码语言：javascript复制HPDataType HPTop(HP* php)
{
return php->a[0];
}删除栈顶的数据
注意：如果直接删除栈顶的数据，整个堆就会变得很乱，所以，删除堆顶的数据用到的方法是：先将栈顶的数据和最后一个孩子交换，然后将最后一个数据删除，删除之后再用向下调整算法将栈顶的数据调到孩子的位置，以满足堆的要求。 向下调整算法
代码语言：javascript复制void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 1;
while (child < size)
{
if (a[child] > a[child 1] && child 1 < size)
{
child ;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 1;
}
else
{
break;
}
}
}删除堆顶的数据
代码语言：javascript复制void HPPop(HP* php)
{
assert(php->size > 0);
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}判断栈是否为空
判断栈是否为空可以直接通过size来判断
代码语言：javascript复制bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}堆的销毁
堆的销毁和顺序表的销毁一样
代码语言：javascript复制void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
