汕头建站程序,自助下单网站怎么做,如何做网站进行推广,品牌整合营销传播前言
本文将会向您介绍关于堆Heap的实现
具体步骤
tips#xff1a;本文具体步骤的顺序并不是源代码的顺序
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;初始化
void HeapCreate(Heap* hp, HPDataType* a, int n)
{hp-本文具体步骤的顺序并不是源代码的顺序
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;初始化
void HeapCreate(Heap* hp, HPDataType* a, int n)
{hp-_a NULL;hp-_size 0;hp-_capacity 0;
}扩容 解析扩容的逻辑很简单没什么可讲的要注意的点有这里不要使用malloc当再次需要扩容的时候malloc函数只会分配新的内存空间不会复制原有内存空间的内容realloc函数会在分配新的内存空间时将原有内存内容复制到新的内存空间中并释放原有空间内容
//扩容
void CheckCapacity(Heap* hp)
{
if (hp-_capacity hp-_size)
{int newcapacity hp-_capacity 0 ? 4 : hp-_capacity * 2;HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(malloc fail);return;}hp-_a tmp;hp-_capacity newcapacity;
}
}判空
// 堆的判空
bool HeapEmpty(Heap* hp)
{assert(hp);return hp-_size 0;
}交换
解析这里提供了一个swap函数用于向上调整和向下调整时交换数据
//交换
void swap(int* a, int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}插入
每次插入的数据都会进行向上调整将一串数据建成小堆/大堆
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{CheckCapacity(hp);hp-_a[hp-_size] x;hp-_size;Adjustup(hp-_a, hp-_size - 1);
}向上调整 当插入数据时注意每次插入一个数据都会向上调整直到根结点图中这里只是将结构画了出来助于理解真实的情况中并不是向右边的堆图一样 以小堆为例当a[child] a[parent]就将二者交换并将parent 赋值给child并利用新的child计算出新的parent这样的做法是可以向上进行调整。这里若是将a[child] a[parent]变成a[child] a[parent]就是大堆
//向上调整
void Adjustup(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){swap(a, a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}删除 解析需要删除堆顶的数据但是如果挪动数据删除堆顶的数据可能会导致可能会导致堆的性质不满足影响堆的正确性和效率。因此需要交换堆顶与末尾的数据再将末尾的数据删除这样一来就可以删除掉堆顶的数据但是有个问题将堆尾的数据调整到了堆顶需要进行向下调整
// 堆的删除 删除堆顶
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));swap(hp-_a, (hp-_a[0]), (hp-_a[hp-_size - 1]));--hp-_size;//向下调整AdjustDown(hp-_a, hp-_size, 0);
}向下调整
解析当我们删除堆顶数据的时候进行向下调整n堆的数据个数利用parent计算出child下标
//向下调整
void AdjustDown(int* a, int n, int parent)
{//计算左child相当于child leftchildint child parent * 2 1;//当逐步地向下调整child会越来越大child不能超过堆数据个数while (child n){//向下调整的时候右child可能越界//找左右child小的那一个进行与a[parent]比较if (child 1 n a[child 1] a[child]){//若是默认的child(leftchild) a[child 1]child;}//可调整(小堆)为大堆if (a[child] a[parent]){swap(a, a[child], a[parent]);//向下调整parent child;child parent * 2 1;}else{break;}}
}销毁
// 堆的销毁
void HeapDestory(Heap* hp)
{free(hp-_a);hp-_a NULL;hp-_capacity 0;hp-_size 0;
}获取堆顶数据
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp-_a[0];
}获取个数
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-_size;
}小结
本文的分享就到这里啦如果本文存在疏漏或错误的地方还请您能够指出
