写在最前

  1. 节点A的高度 h 的定义是, A到叶子节点的边的个数. 所以 1,2,3 这个堆的高度是1

  2. 证明 i 的子节点是 2i+1 和 2i+2 , 可以用数据归纳法证明. 如果对于 i 成立, 那么 i+1 的子节点是 2i+2+1, 2i+2+2 , 所以对 i+1 也成立. 所以 i 的父节点是 floor(i/2)

6.1-1

先来计算高度为 h 的完全二叉树, 元素个数为多少.

第 i 层的元素个数是 2**(i-1) , 设总元素个数 S = 1 + 2 + 4 + ... + 2**(n-1)

2 * S = 2 + 4 + ... + 2**n

S= 2S-S= 2**n-1

因为高度 h=n-1, 所以高度为 h 的堆中, 元素最多是 2**(h+1) - 1 个, 最少是 2**h 个

6.1-2

由 6.1-1 可知, 2**h <= n <= 2**(h+1) - 1 => h <= ln(n) < h+1 => h<=ln(n) && h > ln(n)-1 , 所以 h = ln(n).floor

6.1-3

略吧

6.1-4

叶子结点上

6.1-5

是的, 因为满足定义 A[parent(i)] >= A[i]

6.1-6

不是 6 < 5

6.1-7

i 的父节点是 floor(i/2), 所以从 floor(i/2)+1 的节点都是没有子节点的, 也就是叶子节点