我要招人

去企业版

首页 > 试题广场 >

已知小顶堆：{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
```

查看答案及解析

最爱清明雨上

这个题应该选65吧

发表于 2019-02-10 17:16:03 回复(2)

程序猿Go师傅

这道题比较的坑爹：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:32:07 回复(3)

简繁

应该是65啊

发表于 2019-02-15 17:28:18 回复(2)

夜半小乐曲

我觉得题目是想说62对应位置节点，也就是调整堆后第六个节点的的左子节点。

发表于 2019-03-04 17:11:24 回复(0)

不忘初心2020

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;
            }
        } 
	}
}

发表于 2020-12-11 23:03:42 回复(0)

欧麦阁

完全二叉树中，节点序号为n,左子节点为2n，右子节点为2n+1.感觉应该是65.

发表于 2019-03-07 16:31:08 回复(0)

Anwma

先来看《算法导论》th3中的最大堆示例：

page：103页

题目的最小堆构建过程

32 73

23 42 62 99

14 24 39 43 58 65 80 120

51 58

32 39 73 80

23 24 42 43 62 65 99 120

23 58

24 39 62 80

32 51 42 43 73 65 99 120

----------------------------------

62的左子结点为73

发表于 2023-05-06 18:06:25 回复(0)

hamik

到底是3943，还是39,43，如果是39,43分开的话，73没毛病

发表于 2020-09-19 15:30:41 回复(0)

松ba

是我看错了吗，39，43是分开的啊

发表于 2020-08-25 22:38:38 回复(0)

向往美好未来

<p>题目问的是62对应节点的左子节点，应该是建初始堆时62所在位置的左子节点，不是小顶堆建成之后62的左子节点</p>

发表于 2020-08-05 09:53:11 回复(0)

牛牛6448630

创建堆的时候，不是从堆顶开始调整的

发表于 2019-02-19 15:38:05 回复(0)

ifengzhi

heapify过程从左子孩子开始，则答案为65

发表于 2019-02-18 14:28:00 回复(0)

提交观点

问题信息

京东 2019 Java工程师

上传者：小小

难度：

12条回答 186收藏 2998浏览

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

问题信息

热门推荐

相关试题