堆的下沉终止条件问题

Question

老师你好，堆的siftdown的终止条件while(leftChild(k) < data.getSize())我实在没懂，如果此时索引为k的节点不是叶子节点，那他就会有叶子节点，而所有节点的的索引不都是小于等于data.size吗？ 麻烦你给我讲讲你这终止条件是个啥逻辑，谢谢！

Answer 1

liuyubobobo 2018-09-25 01:23:22

在我们的leftChild方法中，没有判断k是否存在左孩子节点，其实只是返回2*k+1而已。所以这个判断条件的意思是，如果k的左孩子节点的索引2*k+1 >= data.size()的话，说明k已经是叶子节点了（因为他的左孩子节点越界了），说明我们已经来到了整棵完全二叉树的底部：）

加油！：）

• 提问者 慕少7158242 #1

  假定现有一个15个节点的完全二叉树，索引为k=3的节点的左孩子的索引为7，此时也满足，leftChild=7<size=15,而此时索引为3的节点深度为2，这棵树的深度为3，此时这节点并不是叶子节点呀。

• liuyubobobo 回复 提问者 慕少7158242 #2

  不是啊，所以不能退出循环，要继续这个shiftDown的过程啊：）实际做一个测试用例，跟进程序里看一看？：）

• ciphermagic #3

  老师您说：“所以这个判断条件的意思是，如果k的左孩子节点的索引2*k+1小于data.size()的话，说明k已经是叶子节点了（因为他的左孩子节点越界了）”
  
  这里应该说反了，因为这个判断条件是写在 while 中的，这里的意思应该是 当 leftChild(k) < data.getSize() 时，此时的 k 索引位置还不是叶子节点，所有进到 while 循环里处理吧：）

点开查看后面1条评论