这道题比较的坑爹: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]