完全树的结点数n = 2^h - 1
亦有 结点数n = 2*底层结点数 - 1
注：底层结点数x = 2^(h - 1)
堆中i结点的子树大小至多为2n/3的证明
问题：在任一含n个元素的堆中，至多有ceiling(n/(2^(h+1)))个高度为h的节点。
证明：
当堆是满二叉树时：
最底层的元素个数为ceiling(n/2)个，这层高度为0；
倒数第二层元素个数为ceiling(n/4)个，高度为1；
倒数第三层元素个数为ceiling(n/8)个，高度为2；
如此类推，高度为h的，在倒数第h + 1层，元素个数为ceiling(n / 2^(h + 1))。
若堆不是满二叉树，这个数目则总少于ceiling(n / 2^(h + 1))了。
问题：一棵以节点i为根的、大小为n的子树上，i节点的子树大小至多为2n/3（最坏情况：底层恰好半满的时候），怎么证明？
证明：
这里应该是讨论完全二叉树，规定总size为n，要求根的左子树的最大size。（由于右子树size总是<=左子树size）。
那么显然，观察最底层节点数目为0, 1, 2…的情况，显然半满的时候左子树达到了最大。以下求此时左子树的大小：
设底层半满时节点数为x，则再加x个节点，就是满树：n + x = 2x * 2 - 1 = 满树size
可得n = 3x - 1。
满树时，左子树节点数 = (满树size - 1) / 2 = 2x -1 ~= 2n / 3
