首页 > 试题广场 >

已知小顶堆:{51,32,73,23,42,62,99,14

[单选题]
已知小顶堆:{51,32,73,23,42,62,99,14,24,39,43,58,65,80,120},请问62对应节点的左子节点是
  • 99
  • 73
  • 3943
  • 120

这道题比较的坑爹: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
图片说明

所以答案应该是65


编辑于 2019-10-21 21:31:22 回复(2)
理论上应该是65,不知道出题者是如何建堆的……
发表于 2019-03-07 11:46:16 回复(0)
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)
#结果为[14, 23, 62, 24, 42, 65, 99, 51, 32, 3943, 58, 73, 80, 120]
答案应该是65
发表于 2019-02-21 20:21:38 回复(0)
https://blog.csdn.net/hrn1216/article/details/51465270我根据这篇博客构建小顶堆的方法,得出62的左节点的65
发表于 2019-02-21 16:12:39 回复(0)