最后一个叶子节点的索引是不是(n-2)/2？

Question

数组中元素个数为n，索引从0开始的话，最后一个叶子节点的索引为n-1，所以它的父节点索引应该为(n-2)/2，是不是？

Answer 1

liuyubobobo 2017-05-10 14:56:40

是的哦。这一点课程中有误，我发过一个勘误在这里：http://coding.imooc.com/learn/questiondetail/4384.html 同时课程官方的github的代码对这个问题已经更正。

非常抱歉！这个错误在课程升级的时候会在视频里改正过来：）

• 易萧 #1

  刚刚画出图发现对排序结果并没有影响，对于最后一个叶子节点是左节点的话，不论是它本身除以2还是再减去1然后除以2，得到的都是它的父节点，而其余的父节点不需要折半计算来得到；  如果最后一个叶子节点是右节点的话，计算得到它的父节点比它本身的父节点要大1，而这个假的父节点本身也没有子节点了，顶多对它的shiftdown操作是无效的。后续的其它非叶节点还是一样地进行shiftdown。

• 易萧 #2

  好吧。。才看到勘误里已经写了

• liuyubobobo 回复 易萧 #3

  :-) 赞思考！

Answer 2

agjsytt 2018-01-18 15:43:30

我也看出来不对了. 哈哈

Answer 3

提问者 欧拉木大 2017-05-18 16:09:03

好的，非常感谢！