在学习完树后,我进入到堆的学习,总的来说堆就是一种特殊的树,以下是我对堆的一些总结和归纳:
堆:一种有特殊用途的数据结构--用来在一组变化频繁(增删查改频率高)的数据中查找最值
堆的物理层面:表现为一组连续的数组区间
堆的逻辑层面:一颗满完全二叉树
小堆和大堆:满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆;反之,则是小堆,或者小根堆,或者最小堆。当一个堆为大堆时,它的每一棵子树都是大堆
头文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int HPDateType;
typedef struct Heap
{
HPDateType* a;
int size;
int capacity;
}Heap;
// 堆的构建
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestroy(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDateType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDateType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
void HeapInit(Heap* hp)
{
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}
void HeapDestroy(Heap* hp)
{
free(hp->a);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}
1.先判断空间是否充足,空间不够则需要扩容
2.将数据插入到最后一个位置
3.向上调整(重点)
向上调整思路图:
代码实现:
void Swap(HPDateType* x1, HPDateType* x2)
{
HPDateType tmp = 0;
tmp = *x1;
*x1 = *x2;
*x2 = tmp;
}
void AdjustUp(HPDateType* a,int child)
{
int preant = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[preant])
{
Swap(&a[child], &a[preant]);
child = preant;
preant = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(Heap* hp, HPDateType x)
{
assert(hp);
if (hp->capacity == hp->size)//扩容
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDateType* tmp = (HPDateType*)realloc(hp->a, sizeof(HPDateType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
AdjustUp(hp->a, hp->size);//向上调整//小堆
hp->size++;
}
现在可以在test.c中测试一下:
完美实现!
在堆的删除中不是像以前一样删除最后一个元素,我们一般规定在堆的删除中是删除根节点,
所以堆的删除基本思路就是:
1.将根节点和最后一个元素交换
2.size--删除最后一个元素,也就是删除了之前的根节点
3.从根节点开始向下调整
向下调整基本思路:
代码实现:
void AdjustDown(HPDateType* a, size_t size, int n)//向下调整,n为父亲的下标
{
int preant = n;
int child = preant * 2 + 1;//先默认左孩子小于右孩子
while (child<size)
{
if (a[child + 1] < a[child]&&child+1<size)//若右孩子小于左孩子,调整child
{
child++;
}
if (a[child] < a[preant])
{
Swap(&a[child], &a[preant]);
preant = child;
child = preant * 2 + 1;
}
else
{
break;
}
}
}
void HeapPop(Heap* hp)
{
assert(hp);
Swap(&hp->a[0], &hp->a[hp->size-1]);//将根和最后一个元素交换
hp->size--;//删除最后一个元素,也就是之前的根
AdjustDown(hp->a,hp->size,0);//向下调整,小堆
}
放入test.c中测试一下:
完美实现!
HPDateType HeapTop(Heap* hp)
{
return hp->a[0];
}
int HeapSize(Heap* hp)
{
return hp->size;
}
int HeapEmpty(Heap* hp)
{
return hp->size == 0;
}
最后一起放入test.c中检查一哈:
完美实现!
那么堆的实现就告一段落了,快自己打开编译器实践一下把。