java - L&C 的 Java 软件结构中堆的数组实现错误

Question

在 Java Software Structures 3rd Edition Lewis 和 Chase 提出，堆的数组实现适用于少量项目，但在有大量项目的情况下有时会抛出 ArrayIndexOutOfBoundsException。它出现在 ArrayHeap(扩展了 ArrayBinaryTree)中的方法 heapifyRemove() 的第 113 行。

第 113 行:

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

看来 left 有时会离开数组的末尾。如何解决这个问题？

供引用:

ArrayHeap.java

ArrayBinaryTree.java

Answer 1

在检查 left 的索引是否为 null 之前，应该检查数组的大小是否包含 left (从数组的增长方式来看，它看起来总是包含 left 和 right)。我认为这种情况应该被解释为左和右为空。

所以代码应该是

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