德州网站开发培训,网站制作建设飞沐,网站开发的技术内容,石家庄便宜做网站目录
满二叉树与完全二叉树高度h和树中节点个数N的关系
向上调整算法#xff1a;
介绍#xff1a;
复杂度推导#xff1a;
向下调整算法#xff1a;
介绍#xff1a;
复杂度推导#xff1a;
向上调整建堆#xff1a;
介绍#xff1a;
复杂度推导#xff1a;…目录
满二叉树与完全二叉树高度h和树中节点个数N的关系
向上调整算法
介绍
复杂度推导
向下调整算法
介绍
复杂度推导
向上调整建堆
介绍
复杂度推导
向下调整建堆
介绍
复杂度推导 满二叉树与完全二叉树高度h和树中节点个数N的关系 向上调整算法
介绍 函数功能将堆通过向上调整算法使堆成为小堆父亲孩子或大堆父亲孩子堆内父亲孩子-1/2。只要孩子还在堆范围内就不断判断孩子与父亲的关系。若想设置小堆则孩子父亲就执行交换若想设置大堆则孩子父亲就执行交换。 函数参数HeapDataType * a—堆内数据类型首元素的指针 int child—堆底元素孩子 函数返回值无 void AdjustUp(HeapDataType* 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;}}
}
复杂度推导 一次向上调整最多调整高度次数根据满二叉树hlog(N1)完全二叉树hlog(N)1而时间复杂度计算的是最大情况的数量级所以一次向上调整的复杂度为O(logN) 向下调整算法
介绍 函数功能将堆通过向下调整算法使堆成为小堆父亲孩子或大堆父亲孩子使用假设法先假定要交换的元素为左孩子childparent*21若右孩子左孩子则需交换的元素为parent*211。只要孩子还在堆范围内就不断判断孩子与父亲的关系。若想设置小堆则孩子父亲就执行交换若想设置大堆则孩子父亲就执行交换。 函数参数HeapDataType * a—堆内数据类型首元素的指针 int n —堆内元素个数 int parent—堆顶元素父亲 函数返回值无 void Adjustdown(HeapDataType* a, int n, int parent)
{size_t 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;}}
}
复杂度推导 一次向下调整最多调整高度次数根据满二叉树hlog(N1)完全二叉树hlog(N)1而时间复杂度计算的是最大情况的数量级所以一次向下调整的复杂度为O(logN) 向上调整建堆
介绍 前提上几层都是堆 先将数组内所有元素插入堆结构内再从第一个元素到最后一个元素进行遍历对每个元素使用向上调整算法使堆结构成为大堆/小堆 复杂度推导 向下调整建堆
介绍 前提左右子树都是堆 先将数组内所有元素插入堆结构内再从最后一个父亲的位置到第一个父亲的位置进行遍历对每个元素使用向下调整算法使堆结构成为大堆/小堆 复杂度推导
