我没有得到正确的输出,因为 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 代码是错误的请更正我的代码并提前谢谢