inplace heap sort down heapify 是错误的

问题描述 投票:0回答:0

我没有得到正确的输出,因为 down heapify 部分是错误的,所以请纠正我 并提前感谢。

  • 第 1 部分 upheapify 工作正常

  • part2 downheapify 是错误的

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer [] nums= {10,5,8,1,4};
//part1 upheapify
        for(int i=1;i<nums.length;i++) {
            int childIndex=i;
            int parentIndex=(i-1)/2;
            while(childIndex>0) {
                if(nums[parentIndex]<nums[childIndex]) {
                    break;
                }else {
                    int temp=nums[parentIndex];
                    nums[parentIndex]=nums[childIndex];
                    nums[childIndex]=temp;
                }
                childIndex=parentIndex;
                parentIndex=(parentIndex-1)/2;
            }
        }
        System.out.println(Arrays.toString(nums));
//part2 downheapify this part is wrong  
        for(int i=nums.length-1;i>=0;i--) {
            int temp=nums[0];
            nums[0]=nums[i];
            nums[i]=temp;
            int paretnIndex=0;
            int leftIndex=2*paretnIndex+1;
            int rightIndex=2*paretnIndex+2;
            int minIndex=paretnIndex;
            while(minIndex<i && nums[minIndex]<nums[paretnIndex]) {
                if(leftIndex<nums.length &&nums[leftIndex]<nums[minIndex]) {
                    minIndex=leftIndex;
                }
                if(rightIndex<nums.length && nums[rightIndex]<nums[minIndex]) {
                    minIndex=rightIndex;
                }
                if(paretnIndex==minIndex) {
                    break;
                }
                int temp2=nums[paretnIndex];
                nums[paretnIndex]=nums[minIndex];
                nums[minIndex]=temp2;
                
                paretnIndex=minIndex;
                leftIndex=2*paretnIndex+1;
                rightIndex=2*paretnIndex+2;
                
                
                
            }
            
            
        }
        
        System.out.println(Arrays.toString(nums));
    }

我得到了错误的输出,因为 down heapify 代码是错误的请更正我的代码并提前谢谢

java data-structures heapsort
© www.soinside.com 2019 - 2024. All rights reserved.