c++ - 堆:在C++中确定一片叶子

Question

这个解释让我对堆中叶子的确定有点困惑

"请注意我们如何检测堆中的节点是否为叶子。如果堆中的项数至少为 n，但小于 2*n+1，则下标为 n 的节点为这棵二叉树上的一片叶子。”

例如:

值 |5|3|4|2|

找到|0|1|2|3|

所以数组中有 4 个元素，当我滴到元素 2 时，我应该停下来吗？

因为根据等式 2*n + 1，意味着根是 2*root+1 并且必须小于总节点，对吗？

谢谢!

Answer 1

n = 0  Is the heap at least n?      Yes
       Is the heap less than 2*n+1? No
n = 1  Is the heap at least n?      Yes
       Is the heap less than 2*n+1? No
n = 2  Is the heap at least n?      Yes
       Is the heap less than 2*n+1? Yes

通过归纳，您可以知道 n=2 之后的所有内容也是叶节点。反过来想，如果找到最后一个节点的父节点，就知道后面的每一个元素都是叶节点。因此，最后一个非叶节点是索引(3-1)/2 = 1。