网站主页 优帮云,桂林象鼻山的由来,山西住房与建设部网站,泰州专业网站制作公司创建堆的方式有两种#xff0c;一种是一边插入结点#xff0c;一边调用堆的插入方法调整堆#xff0c;这样的时间复杂度就是 O(NlogN)#xff0c;而第二种方式就把时间复杂度缩减到了O(N)#xff0c;它是采用先把结点插入好了#xff0c;然后再来调整堆#xff0c;并不是…创建堆的方式有两种一种是一边插入结点一边调用堆的插入方法调整堆这样的时间复杂度就是 O(NlogN)而第二种方式就把时间复杂度缩减到了O(N)它是采用先把结点插入好了然后再来调整堆并不是一边插入一边调整。 但是从代码层面来看可能会误以为第二种方式的时间复杂度也是O(NlogN)但第二种方式是从下往上建立堆。举个例子如下所示假设堆中存在了N个节点(满足堆的性质)采用第一种方式再创建N个结点那么插入第一个数时就调用了时间复杂度为logN的插入方法插入N个数后时间复杂度为logN。
让我们看看第二种方式会如何 先把N个结点创建到树中把这N个结点具体化我们看到在调整树时第一次是以倒数第二层的结点作为根节点然后来调整这棵子树也就是它的时间复杂度不再是logN了因为远远没到N个结点远远没到整颗树的高度它的时间复杂度应该如下判断在最坏情况下树中每个结点会一直向下查找一直到底假设树高为h,则倒数第二层会向下查找1次倒数第三层会向下查找2次… 倒数第二层结点数为2(h-2),倒数第三层2h-3…
JAVA代码实现
import java.util.ArrayList;
import java.util.Arrays;//必须传入一个Comparable的实现类因为后续会用到类的内部比较器
public class HeapE extends Comparable {Comparable? super E[] list;//堆--存储Comparable的实现类int size; //堆长度int capacity;//堆容量public Heap(int capacity){this.capacitycapacity;size0;listnew Comparable[capacity1];}//初始化public void Init(E value,int index){if(index0){ list[index] value;size;}elsenew RuntimeException(下标越界);}//创建堆public void Build_Max_Heap(){for(int isize/2;i0;i--){int child0;int parent i;Comparable par_X (E) list[i];for(;parent*2 size;parentchild){childparent*2;if(child1size list[child].compareTo((E) list[child1]) -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 isize;i/20;ii/2){if(i1 || list[i/2].compareTo((E)node)1){list[i]node;break;}else{list[i]list[i/2];}}}//删除堆public E Delete(){Comparable DeleteXlist[1];Comparable Xlist[size--];int child1;int parent1;for(;parent*2size;parentchild){childparent*2;if(child1size list[child].compareTo((E)list[child1])-1 )child;if(X.compareTo((E)list[child])-1)list[parent]list[child];elsebreak;}list[parent]X;return (E)DeleteX;}//测试数据public static void main(String[] args) {HeapSSS 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 i1;iheap.size;i)System.out.println(heap.list[i]);}
}
class SSS implements Comparable {int X;Overridepublic int compareTo(Object o) {SSS s2(SSS) o;if(Xs2.X)return 1;if(Xs2.X)return -1;else return 0;}public SSS(int X){this.XX;}Overridepublic String toString() {return SSS{ X X };}
}
