Ошибка в реализации массива кучи в программных структурах Java L & C

Question

В Java Software Structures, 3-е издание . Автор - Льюис и Чейз. Реализация массива кучи работает для небольшого числа элементов, но в случаях с большим количеством элементов иногда возникает исключение ArrayIndexOutOfBoundsException. Это происходит в строке 113 метода heapifyRemove () в ArrayHeap (который расширяет ArrayBinaryTree).

Строка 113:

if ((tree[left] == null) && (tree[right] == null))

Кажется, что left иногда уходит с конца массива. Как это можно исправить?

Для справки:

ArrayHeap.java

ArrayBinaryTree.java

Answer 1

Перед проверкой, является ли индекс left нулевым, следует проверить, содержит ли размер массива left (по мере роста массива он выглядит так, как если бы он всегда включал left и right).Я думаю, что случай должен интерпретироваться так же, как если бы левый и правый были нулем.

Таким образом, код должен быть

if ((left > count) || ((tree[left] == null) && (tree[right] == null)))