首页 > 试题广场 >

已知小顶堆:{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)

这道题比较的坑爹: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)
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)
先来看《算法导论》th3中的最大堆示例:
page:103页
题目的最小堆构建过程

                51

        32                 73

    23 42                 62     99

14 24 39 43     58 65 80 120

                    14

             51            58

    32 39                 73     80

23 24 42 43     62 65 99 120

                  14

             23             58

     24 39             62     80

32 51 42 43     73 65 99 120

----------------------------------
62的左子结点为73
发表于 2023-05-06 18:06:25 回复(0)
到底是3943,还是39,43,如果是39,43分开的话,73没毛病
发表于 2020-09-19 15:30:41 回复(0)
是我看错了吗,39,43是分开的啊

发表于 2020-08-25 22:38:38 回复(0)
<p>题目问的是62对应节点的左子节点,应该是建初始堆时62所在位置的左子节点,不是小顶堆建成之后62的左子节点</p>
发表于 2020-08-05 09:53:11 回复(0)
创建堆的时候,不是从堆顶开始调整的
发表于 2019-02-19 15:38:05 回复(0)
heapify过程从左子孩子开始,则答案为65
发表于 2019-02-18 14:28:00 回复(0)