algorithm - 如何证明 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))