大小堆的概念
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的接口函数
void HeapInit(Heap*st);//堆的初始化
void swap(int* str1, int* str2);//交换两个数据
void Adjustup(int* a, int child);//向上调整
void HeapPush(Heap* st, int x);//插入元素
void AdjustDown(int* a, int n, int parent);//向下调整
bool HeapEmpty(Heap* st);//堆是否为空
int HeapSize(Heap* st);//堆数据个数
void HeapPop(Heap* hp);//堆元素的删除
void HeapDestroy(Heap* st);//堆的销毁
int HeapTop(Heap* st);//堆顶元素
定义堆结构体
typedef struct Heap
{
int* a;
int size;
int capacity;
}Heap;
初始化堆
void HeapInit(Heap*st)
{
st->a = NULL;
st->capacity = 0;
st->size = 0;
}
交换两个数据
void swap(int* str1, int* str2)
{
int tmp = *str1;
*str1 = *str2;
*str2 = tmp;
}
判断堆是否为空
bool HeapEmpty(Heap* st)
{
assert(st);
if (st->size == 0)
{
return true;
}
else
{
return false;
}
}
堆元素的个数
int HeapSize(Heap* st)
{
assert(st);
return st->size;
}
堆的销毁
void HeapDestroy(Heap* st)
{
assert(st);
free(st->a);
st->a = NULL;
st->size = 0;
st->capacity = 0;
}
堆顶元素
int HeapTop(Heap* st)
{
assert(st);
assert(!HeapEmpty(st));
return st->a[0];
}
向上调整
void Adjustup(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
插入数据一般就是插到最后一个，但是插入的数据不能保证该堆还是大堆或者小堆，所以要使用向上调整，举例说明
这是一个小堆
插入一个数据4后
然后就不是堆了，要变成堆，必须将4向上调整，影响的只有他的祖先6和14
4作为向上调整的孩子，他的下标为6，他的父亲14，下标为2，
下标对应关系为 parent = (child – 1) / 2
因为是小堆，如果孩子小于父亲的话，交换孩子与父亲的数据
原来父亲与孩子的关系如下
交换父亲和孩子的数据后，改变孩子和父亲的下标如下
对应操作是 child = parent; parent = (child - 1) / 2;
继续比较孩子和父亲的值，如果孩子小于父亲，就交换.
然后改变父亲与孩子的下标改变
插入数据
void HeapPush(Heap* st, int x)
{
if (st->capacity == st->size)
{
int newcapcity = st->capacity == 0 ? 4 : st->capacity * 2;
int* tmp = (int*)realloc(st->a, newcapcity*sizeof(int));
if (tmp == NULL)
{
perror("realloc fail");
}
st->a = tmp;
st->capacity = newcapcity;
}
st->a[st->size] = x;
st->size++;
Adjustup(st->a, st->size - 1);
}
每插入一个数据向上调整，随时保证他是小堆
向下调整
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
parent= child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
删除数据
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
AdjustDown(hp->a,hp->size, 0);
}
删除数据我们是删除的堆顶数据，如果直接删掉堆顶数据的话，父子关系全部乱套，就不是堆了.
所以我们采取的是将堆顶元素和堆的最后一个元素交换，然后删除最后一个元素，接着描述堆数据个数的size–;接下来就是要调整堆顶数据，让其保证还是小堆.
比如还是之前的例子
要删除堆顶元素时，先交换堆顶元素和堆尾元素
然后删除堆尾元素
然后选取堆顶元素孩子小的.
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
这样保证child下标对应的一定是小孩子，child + 1 < n 这个处理没有右孩子的情况
比如说这里，没有右孩子，child下标范围0-n-1(n为堆数据个数).选出左右孩子中小的，和父亲交换,交换完了，将孩子下标给父亲，孩子的下标更新为孩子的孩子的下标
如果只有一个孩子并且父亲大于孩子
则执行这个
如果孩子大于父亲的话，就已经是小堆了，直接break;
这里循环的条件是child<n,孩子是子叶的时候.
主函数测试
int main()
{Heap hp;
HeapInit(&hp);
int arr[] = {17,25,15,37,45,16,58};
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
for (i = 0; i < sz; i++)
{
HeapPush(&hp, arr[i]);//将数组中的元素压入堆中
}
while (!HeapEmpty(&hp))//如果堆不为空
{
int top = HeapTop(&hp);//取堆顶元素
printf("%d\n", top);//打印堆顶元素
HeapPop(&hp);//删除堆顶元素
}
return 0;
}
编译运行
文章出处登录后可见！
