为最小堆实现构建堆方法时出现问题

Question

我正在尝试制作min-heap算法，我能够让insert、delete、pop、trickeUp和trickeDown方法工作，但我在使用构建堆算法的构造函数方面遇到了问题。

这个方法很简单，因为它只想从数组中构建一个新的堆。此外，我将实现堆排序算法，该算法需要heapify((来维护堆属性。但是，如果构造函数和不确定我的heapify((是否正确，我会被卡住。一旦构造函数工作，堆排序将变得容易实现。

/** Construct a new heap from an array of unsorted data.
* 
* Complexity: O(n)
* @param data       Array to populate the heap from
* @param capacity   Capacity of the heap (must be >= data.length)
* @param comparator Comparator to use when comparing elements
*/
MinHeap(T[] data, int capacity) {

for(int i = data.length/2 + 1; i >= 0;i--){       
heapify(data,i);       
}
}

public  void heapify(Comparable[] data,int i){
int smallest = i;
if(size >left(i) && data[left(i)].compareTo(data[i])< 0 )
{
smallest = left(i);
}
else{
smallest = i;
}
if(size>right(i) && data[right(i)].compareTo(data[i])< 0)
{
smallest = right(i);
}
if(smallest !=i)
{
Comparable temp = data[i];
data[i] = data[smallest];
data[smallest] = temp; 
heapify(data,smallest);
}
}

//////测试文件

@Test public void testArrayConstruction() {
System.out.println("array construction");
for(int i = 0; i < 100; ++i) {
Integer[] data = randomArray(i);
MinHeap h = new MinHeap(data, i*2);
assertEquals(h.capacity(), i * 2);
assertEquals(h.size(), i);
// Collections has min/max, but of course those don't work on arrays.
Integer smallest = data[0];
for(Integer x : data)
if(x < smallest)
smallest = x;                        
checkHeapOrder(h);
assertEquals(h.top(), smallest);           
}
Integer[] randomArray(int size) {
Integer[] arr = new Integer[size];
for (int i = 0; i < size; ++i) {
arr[i] = Math.round((float) Math.random() * Integer.MAX_VALUE);
}
return arr;
}
void checkHeapOrder(MinHeap h) {
assertTrue(h != null);
for(int i = 1; i < h.size() / 2; ++i) 
assertTrue("Heap order property is broken at element at position " 
+ i,
h.data[i].compareTo(h.data[i*2]) < 0 && 
h.data[i].compareTo(h.data[i*2 + 1]) < 0);
}

这是测试文件中出现问题的行：integer minimum=data[0]；这里，该方法无法初始化数组的最小到第0个元素。我试着调整程序，但每次都会出现同样的错误。我认为测试文件也可能是不正确的，所以只想确定一下。

testArrayConstruction caused an Error: 0
java.lang.ArrayIndexOutOfBoundsException

Answer 1

您没有包含randomArray((的代码。。。

假设此方法生成大小等于方法参数的随机化数组，那么您对的调用

Integer[] data = randomArray(0);

生成大小为0的数组。

无法读取索引0处的元素，因为大小为0的数组没有元素。