算法导论堆排序基础问题

Question

算法导论里面第6章，堆排序。习题6.1-2，含有n个元素的堆的高度的求解。。是不是把根那一行算作第0行了？？有第0刚这么一说吗？不都是从第一行起的吗？

Answer 1

 public static void heapSort(int arr[]){
        //初始化堆
        initHeap(arr);
        //System.out.println("初始化堆：" + Arrays.toString(arr));
        //end表示堆的结束位置
        int end = arr.length - 1;
        while(end > 0){
            //删除堆顶元素
            int temp = arr[0];
            arr[0] = arr[end];
            arr[end] = temp;
            end--;
            if(end > 0){
                //调整堆
                adjustHeap(arr,end);
            }
        }
    }
    public static void initHeap(int[] arr){
        //从0计数，则位置i的节点，左孩子在位置2i+1处，右孩子在位置2i+2处，而父节点在(i-1)/2处
        for(int i = 1 ; i < arr.length ; i ++){
            int current = i;
            while(current > 0){
                int parent = (current - 1) / 2;
                //孩子节点大于父节点，则交换位置
                if(arr[current] > arr[parent]){
                    int temp = arr[current];
                    arr[current] = arr[parent];
                    arr[parent] = temp;
                    //向上调整，跟新current
                    current = parent;
                }else{
                    break;
                }
            }
        }
    }
    public static void adjustHeap(int[] arr,int end){
        //删除堆顶元素后，调整堆顶的位置
        //需要知道的是，由于删除堆顶只是调整了堆顶的元素值，
        //因此除去堆顶之后，左右都是符合堆的树，
        //如此将堆顶元素向下调整的时候，如果检测到堆顶元素符合堆的定义时，
        //而由于它的左右子树始终是符合堆的定义，因此调整过程可以结束
        int current = 0;
        while(current < end){   
            int left = current * 2 + 1;
            int right = current * 2 + 2;
            if(left <= end && right <= end){
                //左右节点都存在
                if(!(arr[current] >= arr[left] && arr[current] >= arr[right])){
                    //需要进行调整堆顶
                    int index = left;
                    if(arr[left] < arr[right]){
                        //左节点小于右节点
                        index = right;
                    }
                    int temp = arr[current];
                    arr[current] = arr[index];
                    arr[index] = temp;
                    current = index;
                }else{
                    //此时已经是堆了，无需继续向下调整
                    break;
                }
            }else if(left <= end && right > end){
                //左节点存在但右节点不存在  
                if(arr[current] < arr[left]){
                    int temp = arr[current];
                    arr[current] = arr[left];
                    arr[left] = temp;
                    current = left;
                }else{
                    //此时已经是堆了，无需继续向下调整
                    break;
                }
            }else{
                //左右节点都不存在,已经调整到底了
                break;
            }
        }
    }