堆：确定C++

Question

叶对此的解释是有点迷惑我，叶的决心堆

“通知我们如何可以检测堆一个节点是否为叶若。堆中的项数至少为n，但小于2 * n + 1，那么带下标n的节点就是这个二叉树上的一个叶。

例如：

VAL | 5 | 3 | 4 | 2 |

ind | 0 | 1 | 2 | 3 |

所以在数组中有4个元素，当我滴入元素2时，我应该停止对吗？

因为从等式2 * n + 1，意思是根是2 *根+ 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。