当前位置:   article > 正文

堆排序自下向上建堆和自上向下调整的时间复杂度_自下而上建堆

自下而上建堆

堆排序分为

因为初始化建堆的过程,是一个杂乱无序的数组构成的完全二叉树,所以需要从第一个非叶节点开始与它的叶子节点进行比较,然后移动。不是说每一层选一个根节点进行比较就可以了,是每一层的所有元素都要跟它的左右节点进行比较。这也就导致了它的时间复杂度不是logn,对于重建堆的过程,因为是从最上面的根节点开始进行左右节点的比较,选择一个较小的左节点或者有节点进行交换。而因为只破坏了一层的有序性,另外一边的子树的有序性没有遭到破坏,所以,另外一边不需要进行比较,所以,每一层只需要比较一次,一共logn层,需要比较logn次。而一共会有n个这样的元素会被放到根节点进行这样的操作,得到n*lognn。

插入:堆的插入过程也是在一个有序的堆后面插入一个元素,所以每次只需要跟它的根节点进行比较即可,最多移动的次数是logn次。

删除:这个暂时还不懂

1.初始化建立堆(自下而上建立堆)

2.输出堆顶元素之后,将堆最末的元素跟堆顶元素进行交换

然后对这个数据结构重新建堆,从上往下进行建堆

时间复杂度

        堆排序的时间复杂度,主要在初始化堆过程和每次选取最大数后重新建堆的过程;

          初始化建堆过程时间:O(n)

        推算过程:

        首先要理解怎么计算这个堆化过程所消耗的时间,可以直接画图去理解;

        假设高度为k,则从倒数第二层右边的节点开始,这一层的节点都要执行子节点比较然后交换(如果顺序是对的就不用交换);倒数第三层呢,则会选择其子节点进行比较和交换,如果没交换就可以不用再执行下去了。如果交换了,那么又要选择一支子树进行比较和交换;

        那么总的时间计算为:s = 2^( i - 1 )  *  ( k - i );其中 i 表示第几层,2^( i - 1) 表示该层上有多少个元素(跟堆的重建过程不一样的是,这里对每一层的元素都要进行交换的操作。但是对于堆的重建,只需要选择一个分支进行比较),( k - i) 表示子树上要比较的次数,如果在最差的条件下,就是比较次数后还要交换;因为这个是常数,所以提出来后可以忽略;

        S = 2^(k-2) * 1 + 2^(k-3)*2.....+2*(k-2)+2^(0)*(k-1)  ===> 因为叶子层不用交换,所以i从 k-1 开始到 1;

        这个等式求解,我想高中已经会了:等式左右乘上2,然后和原来的等式相减,就变成了:

        S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

        除最后一项外,就是一个等比数列了,直接用求和公式:S = {  a1[ 1-  (q^n) ] }  / (1-q);

        S = 2^k -k -1;又因为k为完全二叉树的深度,所以 (2^k) <=  n < (2^k  -1 ),总之可以认为:k = logn (实际计算得到应该是 log(n+1) < k <= logn );

        综上所述得到:S = n - longn -1,所以时间复杂度为:O(n)(堆的初始化过程)

自上向下调整堆结构:
        更改堆元素后重建堆时间:O(nlogn)

        推算过程:

 其中h = log2(n+1)-1,第k层结点个数为2k个(当然最后一层结点个数可能小于2h)。第k层的一个结点插入之后需要进行的比较(移动)次数为k。于是总的比较(移动)次数为∑k*2k(k = 0,1,2,...,h)。可以求得∑k*2k(k = 0,1,2,...,h)=(log2(n+1)-2)*(n+1)+2 = O(n*log2n)

可以这么理解,对于第k层的元素,最多需要移动的次数是k次,这样就移动了底层。k层的元素一共有2的k次方,那么需要移动的次数就是k*log2 k次数。


空间复杂度
        因为堆排序是就地排序,空间复杂度为常数:O(1)
---------------------
作者:庾志辉
来源:CSDN
原文:https://blog.csdn.net/yuzhihui_no1/article/details/44258297
版权声明:本文为博主原创文章,转载请附上博文链接!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/734252
推荐阅读
相关标签
  

闽ICP备14008679号