如何证明n个节点的二进制堆中有ceil（n / 2）个叶子？

Question

您如何证明具有n个节点的二进制堆恰好具有⌈n/2⌉个叶节点？

Answer 1

Let x be the height of tree in which case 2^x = no of leaves
=> 2^0 + 2^1+ 2^2 + 2^3 +...2^x = n
=> 2^(x+1) - 1 = n (By sum series power of 2 formula)
=>2^(x+1)= n+1
=> log(n+1) = x+1
=>log(n+1)-1 = x;
=>log(n+1)- log2 =x
x =log(n+1/2)

=> no of leaves = (n+1)/2 (which is 2^(log(n+1/2))