HeapSort 代码片段给出 Index Out of bound 异常

Question

我正在尝试使用以下代码进行堆排序，它给出了 ArrayIndexOutOfBoundsException 异常：

package com.Sorting;

import java.util.Arrays;

public class HeapSort {

    private static int arr[];
    private static int l,r,max,hsize;
    /**
     * @param args
     */
    public static void main(String[] args) {
        int []numbers={55,2,93,1,23,10,66,12,7,54,3};
          System.out.println(Arrays.toString(numbers));
          HeapSort(numbers);
          System.out.println(Arrays.toString(numbers));
    }

    private static void HeapSort(int myarr[]) {
        // TODO Auto-generated method stub
        arr = myarr;
         hsize = arr.length - 1;
        BuildHeap(arr);
        for(int i = hsize;i>0;i--)
        {
            swap(0,i);
            hsize--;
            SatisfyHeap(arr,0);
        }       
        }

    private static void BuildHeap(int[] arr) {
        // TODO Auto-generated method stub
        for(int i = hsize/2; i>=0;i--)
        {
            SatisfyHeap(arr, i);

        }
    }

    private static void SatisfyHeap(int[] arr, int i) {
        // TODO Auto-generated method stub
         l = 2*i;
         r = 2*i+1;
        if(l<=hsize && arr[l]>arr[i])
    //  if(arr[l]>arr[i] && l<=hsize  )
        {
            max = l;
        }
        else
            max = i;
        if(r<=hsize && arr[r]>arr[max])
        {
            max = r;
        }

        if(max!=i)
        {
            swap(i,max);
            SatisfyHeap(arr, max);
        }

    }

    private static void swap(int i, int max) {
        // TODO Auto-generated method stub
        int temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;    
    }
}

如果我只是交换 SatisfyHeap 方法的 if 语句中左侧和右侧使用的表达式，上面的代码不会给出任何错误。也就是说，您可以尝试注释 SatisfyHeap 方法的第三行并取消注释第四行。请帮助理解这个魔法。

Answer 1

简答

这个魔法叫做"short-circuit evaluation"，它是专门为这种情况设计的。

更长的答案

在 Java 和许多其他语言中逻辑编码

if (condition1 && condition2) { 
    do something 
}

等同于

if (condition1) {
    if (condition2) { 
        do something 
    }
}

这里的 "equivalent" 我的意思是如果 condition2 是要计算的东西，如果 condition1 恰好是 false 则不会计算它。从布尔逻辑的角度来看，这也是正确的。这个技巧在两个方面很有用。首先，它通过跳过评估 calculation2 来提高性能。其次，它在您的情况下很有用 condition1 is a "guard condition" for condition2。

另一个例子是许多 Java 开发人员通过以下方式实现的功能 isEmptyString

public static boolean isEmptyString(String s) {
    return (string == null) || (string.length() == 0);
}

如果没有短路逻辑，如果 s 恰好为 null，此表达式将引发 NullPointerException。

您的具体情况（为什么 ArrayIndexOutOfBoundsException？）

你的问题的另一点可能是 "How it happens that there is ArrayIndexOutOfBoundsException at all?"。要回答这个问题，请考虑第一个元素实际上是堆中最大的元素的情况，我们应该将它向下移动到树的最后一层。这个向下移动是由你的 SatisfyHeap 实现的。所以现在假设我们做了最后一次交换，将最大的元素移到了底部。现在，由于 max 已更改，我们将再进行一次递归调用，并在该调用中 i > arr.length / 2 所以 l = 2*i > arr.length 因此发生异常。

旁注，我想说的是，除非您预先分配 arr 比实际堆大小更大，否则独立于 arr.length 存储 hsize 是一个坏主意代码更难理解。

Answer 2

下面给你一个错误

if(arr[l]>arr[i] && l<=hsize )

因为 l 大于数组的大小，您正试图通过传递超出数组边界的 l 来获取数组元素。

以下适合您

if(l<=hsize && arr[l]>arr[i])

因为在if条件下，首先被求值的是表达式l<=hsize。由于 l 大于 hsize，表达式的计算结果为假。由于 if 谓词的两个子句与 && 运算符连接，根据短路规则，甚至不评估第二个子句中的表达式，从而避免使用 out of 访问数组绑定索引。因此你不会收到任何错误。

HeapSort 代码片段给出 Index Out of bound 异常

HeapSort Code snipplet giving Index Out of bound exception

java

indexoutofboundsexception

heapsort