8-4Sift Down的递归写法
来源:8-4 从堆中取出元素和Sift Down
Super波神
2018-08-23
bobo老师,我的递归写法如下。但是用你给的main函数测试多次,总是报一行错“Error”。请问我的递归写法是哪里有问题么,实在看不出。
//递归实现siftDown
private int ComMax(E e1,E e2){ //返回左右子树中元素较大的索引
if (e1.compareTo(e2) > 0)
return data.find(e1);
else
return data.find(e2);
}
public void siftDownRE(int k){
int lindex = leftChild(k);
int rindex = rightChild(k);
if (lindex > data.getSize()) //如果左右子树都没有
return;
if (rindex < data.getSize()){ //左右子树都有
int maxindex = ComMax(data.get(lindex),data.get(rindex)); //返回左右子树中元素较大的索引
data.swap(k,maxindex);
k = maxindex;
siftDownRE(k);
}
else if(lindex < data.getSize() && rindex >= data.getSize()){ //如果没有右子树,只有左子树
if(data.get(k).compareTo(data.get(lindex)) < 0){ //如果k的元素比它的左子树元素小
data.swap(k,lindex); //调换位置
k = lindex;
siftDownRE(k);
}
return;
}
}
1回答
-
liuyubobobo
2018-08-23
我估计你的逻辑问题在一个很小的数据集上也能浮现出来,哪怕只有5个数据。找一个可以复现这个错误的小数据集尝试自己debug调试一下?
我没有具体运行调试,由于你给的是代码片段,我也不确定一些基本假设是否和你一致。但如果你的逻辑和课程保持一致的话,比如递归终止条件就有问题,应该是lindex >= data.getSize()而不是lindex > data.getSize()。
自己耐心调试一下:)调试代码可是开发者的基本功,也是能写出正确算法的重要环节哦:)尤其是现在你的问题能稳定复现。加油!:)
00
相似问题