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()。


自己耐心调试一下:)调试代码可是开发者的基本功,也是能写出正确算法的重要环节哦:)尤其是现在你的问题能稳定复现。加油!:)

0
0

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1699 问题

查看课程