长沙中小企业网站建设,西安专用网站建设,和京东一样的网站,网站建设出现401目录 堆的介绍
堆的概念
堆的性质
堆的结构
堆的向下调整算法
基本思想#xff08;以建小堆为例#xff09; 代码
堆的向上调整算法
基本思想#xff08;以建小堆为例#xff09;
代码 堆功能的实现
堆的初始化 HeapInit
销毁堆 HeapDestroy
打印堆 HeapPrint
…目录 堆的介绍
堆的概念
堆的性质
堆的结构
堆的向下调整算法
基本思想以建小堆为例 代码
堆的向上调整算法
基本思想以建小堆为例
代码 堆功能的实现
堆的初始化 HeapInit
销毁堆 HeapDestroy
打印堆 HeapPrint
堆的插入 HeapPush
堆的删除 HeapPop
获取堆顶的数据 HeapTop
获取堆的数据个数 HeapSize
堆的判空 HeapEmpty 堆的介绍
堆的概念 堆如果有一个关键码的集合K{k0,k1,k2,…,kn-1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足kik2i1且kik2i2或满足kik2i1且kik2i2其中i0,1,2,…则称该集合为堆。 小堆将根结点最小的堆叫做小堆也叫最小堆或小根堆。 大堆将根结点最大的堆叫做大堆也叫最大堆或大根堆。
堆的性质 堆中某个结点的值总是不大于或不小于其父结点的值。 堆总是一棵完全二叉树。
堆的结构 堆的向下调整算法 现在我们给出一个数组逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 但是使用向下调整算法需要满足一个前提 若想将其调整为小堆那么根结点的左右子树必须都为小堆。 若想将其调整为大堆那么根结点的左右子树必须都为大堆。 基本思想以建小堆为例 1.从根结点处开始选出左右孩子中值较小的孩子。 2.让小的孩子与其父亲进行比较。 若小的孩子比父亲还小则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整直到调整到叶子结点为止。 若小的孩子比父亲大则不需处理了调整完成整个树已经是小堆了。 代码
// 定义一个交换函数用于交换两个整数变量的值
void Swap(int* x, int* y)
{// 创建一个临时变量存储x指向的值int tmp *x;// 将y指向的值赋给x指向的位置*x *y;// 将临时变量tmp的值原x的值赋给y指向的位置*y tmp;
}// 定义一个堆的向下调整函数针对小顶堆
void AdjustDown(int* a, int n, int parent)
{// 初始化child为当前节点的左孩子的下标假设左孩子初始时值较小int child 2 * parent 1;// 当孩子节点下标小于数组长度时循环执行以下操作while (child n){// 如果右孩子存在并且右孩子的值小于左孩子的值if (child 1 n a[child 1] a[child]){// 更新child为较小孩子的下标即右孩子child;}// 如果孩子左右中较小的一个的值小于其父节点的值if (a[child] a[parent]){// 使用交换函数交换父节点和较小的孩子节点的值Swap(a[child], a[parent]);// 更新parent为刚交换后较小孩子的下标准备检查新的子树是否满足堆性质parent child;// 重新计算下一个待检查的孩子节点的下标child 2 * parent 1;}else // 如果当前节点以及其子节点均满足堆性质则结束调整{break;}}
} 使用堆的向下调整算法最坏的情况下即一直需要交换结点需要循环的次数为h - 1次h为树的高度。而h log2(N1)N为树的总结点数。所以堆的向下调整算法的时间复杂度为O(logN) 。 上面说到使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行那么如何才能将一个任意树调整为堆呢 答案很简单我们只需要从倒数第一个非叶子结点开始从后往前按下标依次作为根去向下调整即可。 // 建堆过程
for (int i (n - 1 - 1) / 2; i 0; i--)
{// 从最后一个非叶子节点开始依次对每个节点调用向下调整函数// 这样做可以确保整个堆结构满足小顶堆的性质AdjustDown(php-a, php-size, i);
} 在这段代码中 n 表示堆中的元素个数。通过 (n - 1 - 1) / 2 计算得到最后一个非叶子节点的索引。遍历从最后一个非叶子节点到根节点索引为0依次对每个节点执行向下调整操作使得每个节点及其子树构成一个小顶堆。php-a 是指向堆数组的指针php-size 是堆的大小元素个数。调用 AdjustDown 函数逐个对每个父节点进行调整以保证堆的特性。当遍历完成后整个数组便构成了一个小顶堆。 堆的向上调整算法 当我们在一个堆的末尾插入一个数据后需要对堆进行调整使其仍然是一个堆这时需要用到堆的向上调整算法。 基本思想以建小堆为例 1.将目标结点与其父结点比较。 2.若目标结点的值比其父结点的值小则交换目标结点与其父结点的位置并将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大则停止向上调整此时该树已经是小堆了。 代码
// 定义一个交换函数用于交换两个自定义类型 HPDataType 指针所指向的数据
void Swap(HPDataType* x, HPDataType* y)
{// 创建一个临时变量存储x指向的数据HPDataType tmp *x;// 将y指向的数据赋给x指向的位置*x *y;// 将临时变量tmp的数据原x的数据赋给y指向的位置*y tmp;
}// 定义一个堆的向上调整函数针对小顶堆
void AdjustUp(HPDataType* a, int child)
{// 根据孩子节点的下标计算其父节点的下标int parent (child - 1) / 2;// 当孩子节点的下标大于0即未到达根节点时循环执行以下操作while (child 0){// 如果孩子节点的值小于其父节点的值if (a[child] a[parent]){// 使用交换函数交换孩子节点和父节点的数据Swap(a[child], a[parent]);// 更新孩子节点为刚刚交换后的父节点以便继续向上调整child parent;// 重新计算新的父节点下标parent (child - 1) / 2;}else // 如果孩子节点与其父节点的值关系已经满足堆的性质则停止调整{break;}}
} 在上述代码中 HPDataType 是用户自定义的数据类型这里假设它支持 运算符用于比较大小。AdjustUp 函数主要用于将新插入或更新后的元素调整到正确位置以保持小顶堆的性质。从下标为 child 的节点开始如果其值小于父节点则两者交换位置直到无法继续交换即已达到根节点或者不再违反堆的性质。 堆功能的实现
堆的初始化 HeapInit 首先必须创建一个堆类型该类型中需包含堆的基本信息存储数据的数组、堆中元素的个数以及当前堆的最大容量。
// 数据类型定义
typedef int HPDataType; // 定义堆中存储数据的类型为整型// 结构体定义
typedef struct Heap
{// 堆中存储数据的数组动态分配内存来存储堆中的元素HPDataType* a;// 记录堆中已有元素的个数int size;// 记录堆的最大容量即数组a可容纳的元素数量int capacity;
} HP; 创建完堆类型后我们还需要一个初始化函数对刚创建的堆进行初始化注意在初始化期间要将传入数据建堆。
// 定义一个初始化堆的函数
void HeapInit(HP* php, HPDataType* a, int n)
{// 断言检查传入的堆结构指针是否有效assert(php);// 动态申请一块足够容纳n个HPDataType类型数据的内存空间HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType)*n);// 检查内存申请是否成功if (tmp NULL){printf(动态内存分配失败\n);exit(-1); // 若分配失败程序终止运行}// 将新申请的内存空间赋值给堆结构的数组成员php-a tmp;// 使用memcpy函数将输入数组a中的数据复制到堆结构的数组中memcpy(php-a, a, sizeof(HPDataType)*n);// 设置堆的已有元素个数为输入的nphp-size n;// 同时设置堆的容量也为nphp-capacity n;// 初始化堆从最后一个非叶子节点开始依次对每个节点进行向下调整操作int i 0;for (i (php-size - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, php-size, i);}
} 此函数的作用是初始化一个堆结构并根据传入的数据构建一个小顶堆。首先动态分配内存以存储堆中的数据然后将输入数组a中的数据复制到堆结构的数组中。接着设置堆的大小和容量并从最后一个非叶子节点开始使用 AdjustDown 函数对每一个节点进行调整最终使整个数据结构满足小顶堆的性质。 销毁堆 HeapDestroy 为了避免内存泄漏使用完动态开辟的内存空间后都要及时释放该空间所以一个用于释放内存空间的函数是必不可少的。
// 定义一个销毁堆的函数
void HeapDestroy(HP* php)
{// 断言检查传入的堆结构指针是否有效assert(php);// 释放之前动态分配给堆结构数组的空间free(php-a);// 置堆结构的数组指针为空防止野指针问题php-a NULL;// 将堆中元素个数清零php-size 0;// 将堆的容量也清零php-capacity 0;
} 此函数用于销毁堆结构释放堆占用的内存资源并将相关状态信息重置为初始状态以便后续可能的再次初始化或避免产生内存泄漏等问题。 打印堆 HeapPrint 打印堆中的数据这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印即打印成树形结构。
// 计算具有n个节点的完全二叉树的深度
int depth(int n)
{assert(n 0);if (n 0){int m 2;int height 1;while (m n 1){m * 2;height;}return height;}else{return 0;}
}// 打印堆
void HeapPrint(HP* php)
{assert(php);// 按照数组形式打印堆内容int i 0;for (i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);// 按照树形结构打印堆内容int tree_depth depth(php-size);int total_nodes pow(2, tree_depth) - 1; // 获取对应深度的满二叉树的节点总数int current_spaces total_nodes - 1; // 记录每一行前面的空格数int current_row 1; // 当前行数int index 0; // 待打印数据的下标while (true){// 打印前面的空格for (int i 0; i current_spaces; i){printf( );}// 打印数据和间距int nodes_in_row pow(2, current_row - 1); // 每一行的数字个数while (nodes_in_row--){printf(%02d, php-a[index]); // 打印数据if (index php-size) // 如果所有数据都已打印则结束打印{printf(\n);return;}int spaces_between_numbers (current_spaces 1) * 2; // 两个数之间的空格数for (int j 0; j spaces_between_numbers; j) // 打印两个数之间的空格{printf( );}}printf(\n); // 换行current_row; // 下一行current_spaces current_spaces / 2 - 1; // 更新当前行的空格数}
} 这段代码实现了两个功能 depth 函数用于计算具有n个节点的完全二叉树的深度。 HeapPrint 函数用于打印堆的内容。首先按数组顺序打印堆的所有元素然后按照树形结构打印堆使其看起来像一棵二叉树。通过计算堆对应的完全二叉树的深度确定每一层节点的数量及相应空格数从而实现树形结构的打印。 堆的插入 HeapPush 数据插入时是插入到数组的末尾即树形结构的最后一层的最后一个结点所以插入数据后我们需要运用堆的向上调整算法对堆进行调整使其在插入数据后仍然保持堆的结构。
// 插入元素到堆中
void HeapPush(HP* php, HPDataType x)
{// 断言检查堆结构指针有效性assert(php);// 判断堆是否已满如果满了则尝试扩大容量if (php-size php-capacity){// 申请两倍于当前容量的新内存空间HPDataType* tmp (HPDataType*)realloc(php-a, 2 * php-capacity * sizeof(HPDataType));// 检查内存分配是否成功if (tmp NULL){printf(动态内存扩充失败\n);exit(-1); // 分配失败则退出程序}// 成功分配内存后更新堆结构的数组指针和容量值php-a tmp;php-capacity * 2;}// 将新元素添加至堆数组末尾php-a[php-size] x;// 堆大小加一php-size;// 调整堆结构确保新插入元素后的堆仍满足堆属性AdjustUp(php-a, php-size - 1); // 从新增节点开始向上调整
} 在这个函数中我们首先检查堆是否已满若满则通过realloc函数扩大堆容量。接着将新元素添加至堆数组的末尾并增加堆的大小计数。最后调用AdjustUp函数对新插入的元素进行上浮调整确保堆仍然满足小顶堆的性质。 堆的删除 HeapPop 堆的删除删除的是堆顶的元素但是这个删除过程可并不是直接删除堆顶的数据而是先将堆顶的数据与最后一个结点的位置交换然后再删除最后一个结点再对堆进行一次向下调整。 原因我们若是直接删除堆顶的数据那么原堆后面数据的父子关系就全部打乱了需要全体重新建堆时间复杂度为O(N)。 若是用上述方法那么只需要对堆进行一次向下调整即可因为此时根结点的左右子树都是小堆我们只需要在根结点处进行一次向下调整即可时间复杂度为 O(log(N))。
// 删除堆顶元素
void HeapPop(HP* php)
{// 断言检查堆结构指针有效性assert(php);// 断言检查堆是否为空如果不是空堆才能进行删除操作assert(!HeapEmpty(php));// 将堆顶元素即数组的第一个元素与堆的最后一个元素交换Swap(php-a[0], php-a[php-size - 1]);// 删除堆的最后一个元素即将堆大小减一php-size--;// 由于堆顶元素可能不再满足堆的性质因此需要对新的堆顶元素进行向下调整操作以恢复堆的有序性AdjustDown(php-a, php-size, 0);
}此函数首先确认堆不为空然后通过交换堆顶元素和堆尾元素的位置实际上将堆尾元素移到了堆顶。接着减少堆的大小表示删除了堆顶元素最后调用 AdjustDown 函数从新的堆顶元素开始向下调整堆确保剩余元素重新形成符合堆性质的结构。 获取堆顶的数据 HeapTop 获取堆顶的数据即返回数组下标为0的数据。
// 获取堆顶元素的值
HPDataType HeapTop(HP* php)
{// 断言检查堆结构指针有效性assert(php);// 断言检查堆是否为空非空堆才能获取堆顶数据assert(!HeapEmpty(php));// 返回堆顶元素的值即堆数组的第一个元素return php-a[0];
}此函数用于安全地获取堆顶元素的值在确保堆非空的情况下直接返回堆顶元素小顶堆中最小的元素。若堆为空则会触发断言错误提示堆为空无法获取堆顶元素。 获取堆的数据个数 HeapSize 获取堆的数据个数即返回堆结构体中的size变量。
// 获取堆中元素个数
int HeapSize(HP* php)
{// 断言检查堆结构指针有效性assert(php);// 返回堆中当前存储的数据个数return php-size;
}
此函数用于获取堆中实际包含的元素数量只需直接返回堆结构体中的 size 成员变量即可。在调用此函数前需确保堆结构指针有效。 堆的判空 HeapEmpty 堆的判空即判断堆结构体中的size变量是否为0。
// 判断堆是否为空
bool HeapEmpty(HP* php)
{// 断言检查堆结构指针有效性assert(php);// 如果堆中数据个数为0则认为堆为空return php-size 0;
}
此函数用于检查堆中是否有数据通过查看堆结构体中的 size 成员变量是否为0来判断。当堆中没有元素时函数返回 true表示堆为空否则返回 false表示堆中有至少一个元素。在调用此函数前需确保堆结构指针有效。
