证明:n个结点的堆中结点i的子树大小至多为2n/3
堆中结点数目为n,因为做子树数目肯定大于等于右子树数目,所以底层半满时左子树最大(含结点数目最多)
假设高度为h的堆底层正好半满,此时左子树高度为0的结点数目为k个,则右子树中与左子树在同一层的结点数目也为k个(此时为空)
当对是满二叉树时,结点数目为n+k个,高度1-h之间有2^(h)-1个结点,高度0有2^(h) == 2k个结点,因此结点总数为2^h - 1 + 2^(h) = 4*k-1个结点(2*k = 2^(h))
可得:n+k = 4*k -1
n = 3*k - 1
左子树结点数目为:(n+k-1)/2 = (4*k-2)/2 = 2*k - 1 = 2*(n+1)/3 - 1 = (2*n-1)/3 < 2*n/3
因此结点i的子树大小至多为2*n/3