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

妖狐艹你老母 2022-11-07 11:40 221阅读 0赞

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

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

## 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 +
                    '}';
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/acfa853ce69442cd8879e81de02e3a9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/dba546d3fef24427b2178d512a7bf999.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/c0f43589f52a4e8483474415f628416b.png