南阳网站建设xihewh,网站建站 优化,深圳住房宝安和建设局网站,苏州新区做网站#x1f381;个人主页#xff1a;我们的五年
#x1f50d;系列专栏#xff1a;数据结构课程学习
#x1f389;欢迎大家点赞#x1f44d;评论#x1f4dd;收藏⭐文章 目录
#x1f369;1.大堆和小堆
#x1f369;2.向上调整算法建堆和向下调整算法建堆#xff1a;…个人主页我们的五年
系列专栏数据结构课程学习
欢迎大家点赞评论收藏⭐文章 目录
1.大堆和小堆
2.向上调整算法建堆和向下调整算法建堆
向上调整算法
向下调整算法
用这两种方法建堆的时间复杂度
3.堆排序 1.大堆和小堆
要想弄明白堆排序我们先来看看大堆和小堆的概念和区别
注意堆是完全二叉树。
大堆父节点都大于孩子节点。
小堆父节点都小于孩子节点。 2.向上调整算法建堆和向下调整算法建堆
注根节点我定为0
向上调整算法
向下调整算法调整该节点的前提是该节点以上的树已经是堆大堆或者小堆但是开始的时候树里面的元素是随便放置的但是可以把根元素以上看成一个堆然后向上调整从2*01第二层左边的元素的位置开始就可以了。 以向上调整建立大堆为例
从已经建好的堆的下一层开始向上调整这里可以把根看成小堆要想把整个二叉树调整为小堆形式我们就要从根的下一层把每个元素都进行一次向上调整。
向上调整的实现
根该节点开始我们把该节点与它的父节点进行比较因为该节点以上的节点已经是大堆此时的根是该树最大元素所以只要和根比较谁大如果比根大就交换位置这样增加一个元素以后该树还是大堆。 从上面图来看向上调整结束的条件为该节点到达根节点上面没有元素了。
由孩子节点的下标找到父节点的下标是parentchild-1/2。
实现代码
void AdjustUp(int* a,int child)
{//该节点开始比较int parent (child - 1 - 1) / 2;while (child 0) //当节点到达根节点就没有父亲节点了就停止{if (a[parent] a[child]){int tmp a[parent];a[parent] a[child];a[child] a[parent];child parent;parent (child - 1 - 1) / 2;}else{break;}}
}
向下调整算法
向下调整算法的要求就是左右子树已经是堆大堆或者小堆。结束的条件是孩子节点为NULL。
代码为
void AdjustDown(int* a, int size, int parent)
{//假设法int child parent * 2 1;while (child size){if (child 1 size a[child 1]a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
用这两种方法建堆的时间复杂度 假如待排序的二叉树有K层假设为满二叉树 如果用向上调整算法那么进行的次数是 第1层2^0*0 //2的0次方这这一层的节点个数0是调整的次数根节点向上调整的时候 不需要调整。 第2层2^1*1 …… 第K层2^(k-1)*k-1 所以总的次数为 2^0*02^1*12^2*2……2^(k-1)*k(k-1)*2^k-2. 个数N2^k-1.klog2 (N1) 所以ON(log2 (N1)-1)*(N1)-2。 数量级在log N 所以ONN*log N。 向下调整 其实用向下就可以让节点最多的调整次数最少也就是多*少少*多。 而向上调整就是多*多少*少。第一层的节点少不用调整第二层两个节点每个调整一次后面节点多每个节点调整次数也多。 第k-1层2^(k-2)*1。 第k-2层2^(k-3)*2。 …… 第2层2^1*(k-2。 第1层2^0*(k-1)。 总的2^0*(k-1)2^1*(k-2)……2^(k-2)*12^k2*k-4。 ONlog N。 根据上面的结论我们知道如果要建堆那肯定是用向下调整更好。
3.堆排序
用向下排序拍好序以后如果我们要排升序我们就建大堆如果我们要排降序我们就排小队堆。
升序大堆。
降序小堆。
我们以升序为例
当得到大堆的时候根节点是最大的然后我们把根节点和最后的节点换一下位置这样最大的就到最后面去了然后我们换完以后又用向下调整使除最后一个节点以外为大堆这样我们取根节点我们就的得到了第二大的我们就把第二大的和数组的倒数第2的位置换位置然后再让根节点向下调整建立大堆……
这样我们就能让数组升序,代码实现
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void AdjustDown(int* a, int size, int parent)
{//假设法int child parent * 2 1;while (child size){if (child 1 size a[child 1]a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//升序
void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
