堆排序时间复杂度的计算过程_堆重调整的时间复杂度

一、代码实现

关于具体实现过程请点 https://blog.csdn.net/weixin_44324174/article/details/104183349
本片文章只讲堆排序时间复杂度的计算过程。

package com.westmo1.demo2;
import java.util.Arrays;
import java.util.Scanner;
public class MyDemo3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入数据");
        int[] ints = new int[7];
        for (int i = 0; i < ints.length; i++) {
            int i1 = scanner.nextInt();
            ints[i]=i1;
        }
        int length=ints.length-1;
        int root=ints.length/2-1;
        for (int i = root; i >=0; i--) {
            BuildHeap(ints, length, i);
        }
        //取值，把根结点元素和最后一个元素交换
        for (int i = 0; i <ints.length; i++) {
            swap(ints,0,length);
            length--;
            BuildHeap(ints,length,0);
        }
        System.out.println(Arrays.toString(ints));
    }
    //建立大根堆
    public static void BuildHeap(int arr[],int length,int root){
        int leftcode=root*2+1;
        int rightcode=root*2+2;
        int max=root;
        if(leftcode<length&&arr[leftcode]>=arr[max]){
            max=leftcode;
        }
        if(rightcode<length&&arr[rightcode]>=arr[max]){
            max=rightcode;
        }
        if (max!=root) {
            swap(arr,max,root);
            //调整完之后，可能会影响到下面的子树，需再次调整
            BuildHeap(arr,length,max);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

二、时间复杂度的计算

注意：这里计算都是以完满二叉树进行计算的。

1、建堆

建堆的过程都是从倒数第二层最右边的节点开始，每个节点调整位置花费的时间复杂度是O(1),为了方便后面的计算，统计就说是执行1次；然后是倒数第三层，这一层每个节点也需要执行1次，但是因为调整后会影响到它的后面的节点，所以每个节点还需执行1次（这个次数取决于你的代码怎么写，非常关键），这里非常关键。

int max=root;
if(leftcode<length&&arr[leftcode]>=arr[max]){
    max=leftcode;
}
 if(rightcode<length&&arr[rightcode]>=arr[max]){
    max=rightcode;
}
if (max!=root) {
  swap(arr,max,root)
   //调整完之后，可能会影响到下面的子树，需再次调整
   BuildHeap(arr,length,max);
}
1
2
3
4
5
6
7
8
9
10
11
12

上面的代码是调整节点位置的过程，我们发现，这种代码调整之后的结果是：**父节点最后只和它的左孩子节点或右孩子节点的其中一个发生了交换，**所以倒数第三层每个节点的在调整位置的时候，每个节点只会影响到它的右子树或者左子树的结构中的一个，所以执行1次。如果这里的代码采用的是父节点先和左孩子结点比较交换然后再和右孩子节点比较交换的写法，那它最后时间复杂度计算出来的结果就是nlogn；我们是以最优的算法来计算的。
我们以三层结构的完满二叉树举例来推导一下计算公式

所以最后推导出来的公式就是：

S=[2^(k-1)+2^(k-1)*0]+[2^(k-2)+2^(k-2)*1]+[2^(k-3)+2^(k-3)*2]+......+[2^0+2^0*(k-1)]
化简后得:S=2^(k-1)*1+2^(k-2)*2+2^(k-3)*3+.......+2^0*k;
        S=2^0*k+2^1*(k-1)+......+2^(k-2)*2+2^(k-1)*1;   (1)
使用等比数列求和中的错位相减法，两边同乘以2，得:
        2S=2^1*k+2^2*(k-1)+......+2^(k-1)*2+2^k*1;      (2)
(2)式-(1)式可得:S=-2^0*k+2^1+2^2+2^3+.......+2^(k-1)+2^k;
使用等比数列求和公式可得:S=2^(k+1)-k-2;
1
2
3
4
5
6
7

所以建堆的总执行次数就是：S=2^(k+1)-k-2
完满二叉树的节点个数是2的整次幂减1，所以2^k-1=节点个数n，所以高度k=log(n+1);
把k带入S中可得：S=2^(log(n+1)+1)-log(n+1)-2,化简得S=2n-log(n+1)；
所以建堆的时间复杂度为O(n);

2、取值后重新调整堆

取值每次取的都是堆顶元素，取完重新调整的次数都是k次，时间复杂度就是也就是logn，而循环要执行n次，所以取值后重新调整堆得时间复杂度就是O(nlogn);

综上所述，堆排序的时间复杂度就是O(n(logn+1))就是O(nlogn);

完全都是个人理解，网上搜了好多，自己都没看的太懂，后来自己摸索着搞了搞，哪里有问题还请指正。