爱主题wordpress,长沙电商优化,影城网站建设,网站运营目标文章目录 目录 文章目录 前言 小堆#xff1a; 大堆#xff1a; 二、使用步骤 1.创建二叉树 2.修改为堆 3.向上调整 结果实现 总结 前言
我们已经知道了二叉树的样子#xff0c;但是一般的二叉树是没有什么意义的#xff0c;所以我们会使用一些特殊的二叉树来进行实现 大堆 二、使用步骤 1.创建二叉树 2.修改为堆 3.向上调整 结果实现 总结 前言
我们已经知道了二叉树的样子但是一般的二叉树是没有什么意义的所以我们会使用一些特殊的二叉树来进行实现而堆就为特殊的二叉树来表示的。 一、堆是什么
堆是一种特殊的二叉树由完全二叉树来表示分为小堆和大堆的表现形式小堆的表现形式为父节点比孩子节点要小下面的根节点同样满足这个条件大堆与之相反父节点要比孩子节点大根节点同样满足条件。
小堆 大堆 二、使用步骤
1.创建二叉树
创建堆我们首先需要创建一个二叉树我们可以使用数组的形式来表示二叉树逻辑结构上我们将数组看为二叉树的形式物理结构上还为数组我们现在需要将其修改为堆。
2.修改为堆
我们需要得知其的父节点个子节点可以举例为第一个节点为父节点下标为0子节点的下标为1和2。当父节点下标为1时子节点下标3和4。由此可以推出公式
父节点(子节点-1)/2
子节点父节点*21
通过这两个公式我们就可以试着将二叉树修改为堆。
3.向上调整
我们建造一个小堆要使父节点比子节点都要小我们可以通过子节点和父节点进行对比如果子节点更小的话就将其进行交换我们可以通过公式由子节点来找到父节点来进行实现结束条件就为子节点小于或等于0时。
void Adjiustup(typedata* ps, int child)
{int parent (child - 1) / 2;while (child 0){if (ps[child] ps[parent]){Swap(ps[child], ps[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
结果实现
运行结果如图所示成功创建小堆如果要创建大堆的话只需要修改子节点和父节点的比较条件即可。 总结
一般的二叉树是没有什么意义的这个堆我们可以根据其的特性进行一些有意义的事情希望我的这篇文章对您有所帮助如有错误欢迎指出。
