Error in array implementation of heap in L&C's Java Software Structures

Question

In Java Software Structures 3rd Edition by Lewis and Chase the array implementation of a heap works for small numbers of items, but in cases with a large number of items sometimes throws a ArrayIndexOutOfBoundsException. It occurs in line 113 of the method heapifyRemove() in ArrayHeap (which extends ArrayBinaryTree).

Line 113:

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

It seems that left sometimes walks off the end of the array. How could this be fixed?

For reference:

ArrayHeap.java

ArrayBinaryTree.java

Roger Lindsjö · Accepted Answer · 2011-12-09 18:52:11Z

1

Before checking if the index for left is null it should check if the the size of the array contains left (from how the array grows it looks like it would always include left and right). I think that case should be interpreted the same as if left and right are null.

So the the code should be

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

answered Dec 9, 2011 at 18:52

Roger Lindsjö

11.6k1 gold badge46 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ciferkey Over a year ago

Thank you very much sir. This works perfectly! I'll have to submit it to the Pearson Books errata page.

Collectives™ on Stack Overflow

Error in array implementation of heap in L&C's Java Software Structures

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related