8-4节中的SiftDown使用递归更加简便

Question

private void siftDown(Integer index){
    //获取出左边孩子和右边孩子的节点索引
    Integer leftIndex = leftChild(index);
    if (leftIndex > array.getSize()-1) return;
    Integer rightIndex =rightChild(index);
    if (rightIndex > array.getSize()-1) return;
    if (array.get(leftIndex).compareTo(array.get(index)) > 0 ){
        array.swap(leftIndex,index);
        siftDown(leftIndex);
    }else if (array.get(rightIndex).compareTo(array.get(index))>0){
        array.swap(rightIndex,index);
        siftDown(rightIndex);
    }
}

使用递归更好理解一点。

Answer 1

liuyubobobo 2018-07-04 14:29:38

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

加油！

• 提问者 xiaocui_0001 #1

  老师，我这里在使用递归的时候有个疑问，之前看到说递归的使用时有一定空间上的消耗，而且从循环来说判断时间复杂度可能比较好判断，那如果是递归操作的时间复杂度判断是如何判断呢？还有个问题就是既然递归消耗一定的空间那是否存在递归算法的时间复杂度比非递归的写法时间复杂度更加复杂，也就时递归的写法不如使用非递归写法。什么时候使用递归更好 什么时候使用非递归更好？

• liuyubobobo 回复 提问者 xiaocui_0001 #2

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

Answer 2

JKwar 2019-07-14 13:05:19

//终止条件
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);
}

Answer 3

仙女座舜 2018-07-19 13:08:59

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);
  }

 }

Answer 4

提问者 xiaocui_0001 2018-07-04 22:15:21

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);
    }
}

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

• 仙女座舜 #1

  你确定运行后没有出错吗

• 仙女座舜 #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);
  		}
  
  	}
  这个代码比较短