HeapSort 代码片段给出 Index Out of bound 异常
HeapSort Code snipplet giving Index Out of bound exception
我正在尝试使用以下代码进行堆排序,它给出了 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
方法的第三行并取消注释第四行。请帮助理解这个魔法。
简答
这个魔法叫做"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
是一个坏主意代码更难理解。
下面给你一个错误
if(arr[l]>arr[i] && l<=hsize )
因为 l
大于数组的大小,您正试图通过传递超出数组边界的 l
来获取数组元素。
以下适合您
if(l<=hsize && arr[l]>arr[i])
因为在if
条件下,首先被求值的是表达式l<=hsize
。由于 l
大于 hsize
,表达式的计算结果为假。由于 if
谓词的两个子句与 &&
运算符连接,根据短路规则,甚至不评估第二个子句中的表达式,从而避免使用 out of 访问数组绑定索引。因此你不会收到任何错误。
我正在尝试使用以下代码进行堆排序,它给出了 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
方法的第三行并取消注释第四行。请帮助理解这个魔法。
简答
这个魔法叫做"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
是一个坏主意代码更难理解。
下面给你一个错误
if(arr[l]>arr[i] && l<=hsize )
因为 l
大于数组的大小,您正试图通过传递超出数组边界的 l
来获取数组元素。
以下适合您
if(l<=hsize && arr[l]>arr[i])
因为在if
条件下,首先被求值的是表达式l<=hsize
。由于 l
大于 hsize
,表达式的计算结果为假。由于 if
谓词的两个子句与 &&
运算符连接,根据短路规则,甚至不评估第二个子句中的表达式,从而避免使用 out of 访问数组绑定索引。因此你不会收到任何错误。