4回答

liuyubobobo

2018-07-04

已采纳

赞！如果感觉递归比迭代好理解，对递归就已经掌握的相当好了：）

加油！

2

2

liuyubobobo

回复

xiaocui_0001

1）关于递归算法的时间复杂度计算，可以搜索“主定理”（Master Theorem），是严谨的递归算法时间复杂度计算的通用数学方法。2）如果递归算法和非递归算法等价的话，二者的复杂度（大O意义下）是一定相等的。但是存在由于递归算法消耗更多的空间，使得递归方法不如非递归方法的情况。（实际上，通常递归算法的效率都会略低于非递归，一方面是递归函数调用的额外开销，另一方面是系统栈的调用）。3）在递归深度不会恶化成O(n)的时候，通常使用递归算法都问题不大。递归的优势就是对于很多复杂的问题，语意更清晰，理解起来更容易，写起来也更容易：）

2018-07-05

共2条回复

JKwar

2019-07-14

//终止条件
if (leftChild(f) >= array.getSize()) {
 return;
}
int cur = leftChild(f);
if (cur + 1 < array.getSize() && array.get(cur + 1).compareTo(array.get(cur)) > 0) {
 cur++;
}
if (array.get(cur).compareTo(array.get(f)) > 0) {
 array.swap(f, cur);
 rsSiftDown(cur);
}

0

0

仙女座舜

2018-07-19

public void siftDown(int k) {
  if (eftChild(k) > data.getSize() - 1) {
   return;
  }
  int j = leftChild(k);
  if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
   j = rightChild(k);
  }
  if (data.get(j).compareTo(data.get(k)) > 0) {
   data.swap(k, j);
   siftDown(j);
  }

 }

0

0

xiaocui_0001

提问者

2018-07-04

private Integer getMaxNode(Integer index){
    Integer leftIndex = leftChild(index);
    Integer rightIndex =rightChild(index);
    Integer compareIndex = leftIndex;
    //如果右孩子比左孩子大 则切换待比较索引
    if (rightIndex < array.getSize()-1 && array.get(leftIndex).compareTo(array.get(rightIndex)) < 0) {
        compareIndex = rightIndex;
    }
    //比较需要比较的索引和父节点比较数据即可
    if (array.get(index).compareTo(array.get(compareIndex))<0)  {
        if (compareIndex .equals(leftIndex)) return 1;
        return 2;
    }else {
        return 0;
    }
  }
  private void siftDown(Integer index){
    //获取出左边孩子和右边孩子的节点索引
    Integer leftIndex = leftChild(index);
    Integer rightIndex =rightChild(index);
    Integer nodeIndex =  getMaxNode(index);//判断3个节点谁最大
    if (nodeIndex ==1){
        //左边
        array.swap(leftIndex,index);
        siftDown(leftIndex);
    }
    if (nodeIndex ==2){
        //右边
        array.swap(rightIndex,index);
        siftDown(rightIndex);
    }
}

修正一下。之前的递归有问题。递归哪边需要取决于 父节点和左右结点互相比较 取最大的值 进行递归。虽然代码比较多 但是递归理解下沉的这个操作简单多了。

0

2

仙女座舜

public void siftDown(int k) { if (k > data.getSize() - 1 || leftChild(k) > data.getSize() - 1) { return; } int j = leftChild(k); if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) { j = rightChild(k); } if (data.get(j).compareTo(data.get(k)) > 0) { data.swap(k, j); siftDown(j); } } 这个代码比较短

2018-07-19

共2条回复