一、创建堆的时间复杂度比较

1、使用offer创建堆：时间复杂度为，其中n为满二叉树的结点数

核心代码：

/*** 上浮* @param childIndex*/private void floatUp(int childIndex){int parentIndex=getParentIndex(childIndex);int currIndex=childIndex;// 不让childIndex发生变动while(parentIndex!=-1&& elements[currIndex].compareTo(elements[parentIndex])>0){swap(currIndex, parentIndex);currIndex=parentIndex;parentIndex=getParentIndex(currIndex);}}@Overridepublic void offer(T data) {elements[size++]=data;// 上浮floatUp(size-1);}

2、使用heapify创建堆（堆化）:时间复杂度为，其中n为满二叉树的结点数

核心代码：

/*** 堆化过程：将一个杂乱的数组变成堆* @param elements*/public Heap(T[] elements) {this.elements = elements;this.size=elements.length;for(int i= size/2-1;i>=0;i--){heapify(size, i);}}private void heapify(int len,int index){int currIndex = index;int leftIndex = getLeftIndex(currIndex);int rightIndex = leftIndex + 1;int  highIndex = currIndex;// 获取父、子中最大值的索引if(leftIndex<len&& elements[leftIndex].compareTo(elements[highIndex])>0)highIndex=leftIndex;if(rightIndex<len&& elements[rightIndex].compareTo(elements[highIndex])>0)highIndex=rightIndex;if(highIndex != currIndex){swap(highIndex, currIndex);// heapify(len, highIndex);作用是调整从父结点位置到子节点位置上的元素下沉到合适的位置heapify(len, highIndex);// 递归语句放在递归方法的最后一个位置可以不用谢递归终止条件}}

3、两种方式的时间复杂度比较：

（1）测试代码：

public static void main(String[] args) {Set<Integer>set=new HashSet<>();// HashSet中不会有重复元素的原因是HashSet中的值是底层实现HashSet的HashMap的键值Random ran = new Random(System.currentTimeMillis());// 将时间值设置为随机数的种子值while(set.size()<1000000){set.add(ran.nextInt(1000000) + 1);}Heap<Integer>heap=new Heap<>();// Set具有元素无序性和元素不重复性long s1 = System.currentTimeMillis();// Java系统当前的毫秒数// 增强for循环for(int tmp : set){heap.offer(tmp);}long s2 = System.currentTimeMillis();System.out.println("offer : " + (s2-s1)+"ms");Integer[] a = new Integer[set.size()];/*set.forEach(e->a[index++]=e);// lambda表达式要求内部类中的参数(如:index)是不可变的*/int index = 0;for(int t : set){a[index++] = t;}Heap<Integer>heap1 = new Heap<>(a);System.out.println("--------------------------");System.out.println(heap.peek());System.out.println(heap1.peek());}

（2）结果输出：