数据结构堆的时间复杂度(最大堆，最小堆)_最大堆时间复杂度

创建堆的方式有两种，一种是一边插入结点，一边调用堆的插入方法调整堆，这样的时间复杂度就是
O(NlogN)，而第二种方式就把时间复杂度缩减到了O(N)，它是采用先把结点插入好了，然后再来调整堆，并不是一边插入一边调整。
但是从代码层面来看，可能会误以为第二种方式的时间复杂度也是O(NlogN)，但第二种方式是从下往上建立堆。举个例子，如下所示，假设堆中存在了N个节点(满足堆的性质)，采用第一种方式，再创建N个结点，那么插入第一个数时，就调用了时间复杂度为logN的插入方法，插入N个数后，时间复杂度为logN。

让我们看看第二种方式会如何？
先把N个结点创建到树中，把这N个结点具体化，我们看到在调整树时，第一次是以倒数第二层的结点作为根节点，然后来调整这棵子树，也就是它的时间复杂度不再是logN了，因为远远没到N个结点，远远没到整颗树的高度，它的时间复杂度应该如下判断，在最坏情况下，树中每个结点，会一直向下查找，一直到底，假设树高为h,则倒数第二层会向下查找1次，倒数第三层会向下查找2次…
倒数第二层结点数为2^(h-2),倒数第三层2^h-3…

JAVA代码实现

import java.util.ArrayList;
import java.util.Arrays;

//必须传入一个Comparable的实现类，因为后续会用到类的内部比较器
public class Heap<E extends Comparable> {
    Comparable<? super E>[] list;//堆--存储Comparable的实现类
    int size;  //堆长度
    int capacity;//堆容量

    public Heap(int capacity){
        this.capacity=capacity;
        size=0;
        list=new Comparable[capacity+1];
    }

    //初始化
    public void Init(E value,int index){
        if(index>0)
        { list[index]= value;
          size++;
        }
        else
            new RuntimeException("下标越界");
    }

    //创建堆
    public void Build_Max_Heap(){
       for(int i=size/2;i>0;i--){
           int child=0;
           int parent = i;
           Comparable par_X= (E) list[i];
           for(;parent*2 <= size;parent=child){
               child=parent*2;
               if(child+1<=size && list[child].compareTo((E) list[child+1]) ==-1)
                   child++;
               if(par_X.compareTo((E) list[child])==1)
                   break;
               list[parent]=list[child];
           }
           list[parent]=(E) par_X;
       }
    }

    //插入堆
   public void Insert(E node){
        list[++size]=node;
        for(int i=size;i/2>=0;i=i/2){
            if(i==1 || list[i/2].compareTo((E)node)==1){
                 list[i]=node;
                 break;
            }
            else{
                list[i]=list[i/2];
           }
        }
   }

   //删除堆
   public E Delete(){
        Comparable DeleteX=list[1];
        Comparable X=list[size--];
        int child=1;
        int parent=1;
        for(;parent*2<=size;parent=child){
            child=parent*2;
            if(child+1<=size && list[child].compareTo((E)list[child+1])==-1 )
                child++;
            if(X.compareTo((E)list[child])==-1)
                list[parent]=list[child];
            else
                break;
        }
        list[parent]=X;
        return (E)DeleteX;
   }

    //测试数据
    public static void main(String[] args) {
        Heap<SSS> heap = new Heap<>(10);
        heap.Init(new SSS(1),1);
        heap.Init(new SSS(2),2);
        heap.Init(new SSS(3),3);
        heap.Init(new SSS(4),4);
        heap.Init(new SSS(5),5);
        heap.Insert(new SSS(6));
        heap.Build_Max_Heap();
        heap.Delete();
        for(int i=1;i<=heap.size;i++)
            System.out.println(heap.list[i]);
    }
}
class SSS implements Comparable {
   int X;

    @Override
    public int compareTo(Object o) {
        SSS s2=(SSS) o;
        if(X>s2.X)
            return 1;
        if(X<s2.X)
            return -1;
        else return 0;
    }
    public SSS(int X){
        this.X=X;
    }

    @Override
    public String toString() {
        return "SSS{" +
                "X=" + X +
                '}';
    }
}

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115