这道题比较的坑爹:1.答案是错的 2.考察小顶堆可以用个小一点的数据,没必要整这么大一个堆来考嘛;
接下来我会用代码来证明为什么答案是错的:
首先定义minHeapify,用于给某个节点建小堆
public void minHeapify(List<Integer> array , int index , int len){ // 取得当前节点的左右子节点索引 int left = left(index); int right = right(index); // 找到index,left,right中最小的值,索引为min int min = 0 ; // 1. 比较左值array[left]和array[index]的大小 if(left < len && array.get(left) < array.get(index)){ min = left; }else{ min = index; } // 2. 比较右值array[right]和array[min]的大小 if(right < len && array.get(right) < array.get(min)){ min = right; } // 3. 如果不是最小堆那么需要继续构造最小堆 if(min != index){ swap(array,min,index); minHeapify(array,min,len); } }
然后定义buildMinHeap来遍历非叶子节点构建最小堆
public void buildMinHeap(List<Integer> array){ // 构建最小堆,将堆的所有非叶子节点都遍历一遍构建最小堆 int len = array.size(); for(int index = len/2 -1 ; index>=0 ; index--){ minHeapify(array,index,len); } }
然后执行main函数测试buildMinHeap
public static void main(String[] args) { MinHeap heap = new MinHeap(); // 测试buildMinHeap List<Integer> array = new ArrayList<>(); array.add(51); array.add(32); array.add(73); array.add(23); array.add(42); array.add(62); array.add(99); array.add(14); array.add(24); array.add(3943); array.add(58); array.add(65); array.add(80); array.add(120); System.out.println("before"); array.forEach(temp-> System.out.println(temp)); heap.buildMinHeap(array); System.out.println("after:"); array.forEach(temp-> System.out.println(temp)); }
最终输出的结果是:
14
23
62
24
42
65
99
32
51
3943
58
73
80
120
class Main { private int[] getMinBinaryHeap(int[] array){ int N = array.length; int minBinaryHeap[] = new int[N]; int root;//根的值 int heapSize = 0;//记录插入位置 for(int num : array){ minBinaryHeap[heapSize]=num; ++heapSize; int pointer = heapSize-1;//当前指向的数组元素位置 while(pointer!=0){ int leafPointer = pointer;//叶子节点位置 pointer = (pointer-1)/2;//根节点位置 root = minBinaryHeap[pointer];//根节点 if(num>=minBinaryHeap[pointer]){//永远把当前数组元素看成叶子与其根比较或者换位 break; }//如果根比叶子大 就交换位置 minBinaryHeap[pointer] = num; minBinaryHeap[leafPointer] = root; } } return minBinaryHeap; } public static void main(String[] args) { int[] tree=new Main().getMinBinaryHeap(new int[]{51,32,73,23,42,62,99,14,24,39,43,58,65,80,120}); for(int i=0;i<tree.length;i++){ if(tree[i]==62){ System.out.println(tree[(i+1)*2-1]); break; } } } }