Фрагмент кода 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;    
    }
}

Приведенный выше код не выдает никакой ошибки, если я просто поменяю местами выражения, используемые слева и справа в if заявление о SatisfyHeap метод. то есть вы можете попробовать прокомментировать третью строку SatisfyHeap метод и раскомментируйте четвертую строку. Пожалуйста, помогите понять эту магию.

Answer 1

Короткий ответ

Магия называется "оценкой короткого замыкания" и была разработана специально для подобных случаев.

Более длинный ответ

В Java и многих других языках логически код

if (condition1 && condition2) { 
    do something 
}

эквивалентно

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

Под "эквивалентным" здесь я имею в виду, что если condition2 что-то вычисляется, оно не будет вычислено, если condition1 бывает false, Также это правильно с точки зрения логической логики. Этот трюк полезен в двух отношениях. Во-первых, это повышает производительность, пропуская оценку calculation2, Во-вторых, это полезно в таких случаях, как у вас condition1 это "условие охраны" для condition2,

Другой пример - функция isEmptyString это реализовано многими Java-разработчиками следующим образом

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

Без короткой логики это выражение подняло бы NullPointerException если s бывает нулевым.

Ваш конкретный случай (почему ArrayIndexOutOfBoundsException совсем?)

Другой вопрос вашего вопроса может быть "Как это происходит, что есть ArrayIndexOutOfBoundsException вообще?". Чтобы ответить на этот вопрос, рассмотрим случай, когда самый первый элемент на самом деле является самым большим в куче, и мы должны переместить его вниз к последнему слою дерева. Это движение вниз осуществляется вашим SatisfyHeap, Итак, теперь предположим, что мы сделали последний обмен, который переместил самый большой элемент вниз. Сейчас как max был изменен, мы сделаем еще один рекурсивный вызов и в этом вызове i > arr.length / 2 так l = 2*i > arr.length и, таким образом, исключение происходит.

Дополнительное замечание, я бы сказал, что если вы заранее не выделите arr быть больше, чем фактический размер кучи hsize независимо от arr.length плохая идея, которая затрудняет понимание кода.

Answer 2

Следующее дает вам ошибку

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

так как l больше, чем размер массива, и вы пытаетесь получить элемент массива, передавая l который выходит за границы массива.

Следующие работы для вас

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

потому что в if условие, первое, что оценивается, это выражение l<=hsize, поскольку l больше, чем hsize, выражение оценивается как ложное. Поскольку два пункта вашего if Предикат соединяются с && оператор, согласно правилам короткого замыкания, выражение во втором предложении даже не оценивается, что избавляет вас от доступа к массиву с индексом вне границ. Поэтому вы не получите никакой ошибки.