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

7个回答

添加回答
这个题应该选65吧
发表于 2019-02-10 17:16:03 回复(2)

这道题比较的坑爹: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-02-20 10:35:45 回复(3)
应该是65啊
发表于 2019-02-15 17:28:18 回复(1)
完全二叉树中,节点序号为n,左子节点为2n,右子节点为2n+1.感觉应该是65.
发表于 2019-03-07 16:31:08 回复(0)
我觉得题目是想说62对应位置节点,也就是调整堆后第六个节点的的左子节点。
发表于 2019-03-04 17:11:24 回复(0)
创建堆的时候,不是从堆顶开始调整的
发表于 2019-02-19 15:38:05 回复(0)
heapify过程从左子孩子开始,则答案为65
发表于 2019-02-18 14:28:00 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号