关于测试用例的问题
来源：8-4 从堆中取出元素和Sift Down
那条时光流过的小巷
2019-07-22
在8-4节中的main函数，测试用例中，比较相邻两个数大小，若前一个小于后一个，则报错。
for(int i = 0 ; i < n ; i ++) {
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
}
int[] arr = new int[n];
for(int i = 0 ; i < n ; i ++) {
arr[i] = maxHeap.extractMax();
}
for(int i = 1 ; i < n ; i ++) {
if(arr[i-1] < arr[i]) {
throw new IllegalArgumentException("Error");
}
}那么在上面的堆结构中，索引4的大小是比索引5的小，那么这样也会报错才对，请问这种测试用例比较相邻2个数是否有问题呢？
写回答
1回答
-
我可能没有特别理解你的问题。
在堆结构中，索引4和索引5的大小是没有关系的。堆结构只保证自己和父亲节点之间的关系。最大堆，自己肯定比父亲节点小，或者自己肯定比孩子节点大。但是兄弟之间，没有固定关系。
以下都是合法的最大堆。
66 / \ 16 50
66 / \ 50 16
但是，我们通过extractMax把元素从堆中取出来，是不一样的。我们按照取出来的顺序放到数组中，数组中的位置和这些元素在堆中本来的位置没有关系。最大堆的性质保证了，元素肯定会从大到小取出来。取出来以后，会使用ShiftDown机制重新组织堆。
如果觉得理解的不够透彻，强烈建议每次调用extractMax后，实际看一下堆中的data是什么样子的？为什么会变成这个样子？最后堆中的数据是怎么组织成arr中的数据的样子的？
继续加油！：）
012019-07-22
相似问题