这道题比较的坑爹: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
import heapq ans = [] l = [51,32,73,23,42,62,99,14,24,3943,58,65,80,120] for i in l: heapq.heappush(ans,i)答案应该是65#结果为[14, 23, 62, 24, 42, 65, 99, 51, 32, 3943, 58, 73, 80, 120]