TAOCP 5.2.3 Exercise 20
We consider a heap of size \(N\) stored in an array \(1,2,\ldots,N\) as a complete binary tree: the root is at index \(1\); for any node \(k\), its left child is \(2k\) and its right child is \(2k+1\)...
Section 5.2.3: Sorting by Selection
Exercise 20. [M20] Prove that (14) gives the special subtree sizes in a heap.
Verified: no
Solve time: 11m52s
Solution
We consider a heap of size (N) stored in an array (1,2,\ldots,N) as a complete binary tree: the root is at index (1); for any node (k), its left child is (2k) and its right child is (2k+1) (provided these indices do not exceed (N)). The left subtree of the root is the tree rooted at node (2); the right subtree of the root is the tree rooted at node (3).
Let (h = \lfloor \lg N \rfloor). Then (2^h \le N < 2^{h+1}). Write [ N = 2^h + l,\qquad 0 \le l < 2^h. ] The tree has (h+1) levels (numbered (0) to (h)). Levels (0) through (h-1) are completely filled; they contain [ 2^h - 1 \quad \text{nodes}. ] Level (h) (the last level) therefore contains the remaining [ N - (2^h - 1) = l + 1 \quad \text{nodes}, ] filled from left to right.
The left subtree of the root consists of two parts:
-
The perfect part. The nodes of the left subtree that lie in levels (1) to (h-1) form a perfect binary tree of height (h-2). This perfect tree contains [ 2^{h-1} - 1 \quad \text{nodes}. ]
-
The last‑level nodes belonging to the left subtree. The last level of the whole tree has (l+1) nodes. The left half of this level (which belongs to the left subtree) can accommodate at most (2^{h-1}) nodes. Because the last level is filled from left to right, the number of nodes actually present in the left half is [ \min(l+1,; 2^{h-1}). ]
Adding these two contributions gives the size of the left subtree: [ L = (2^{h-1} - 1) + \min(l+1,; 2^{h-1}). ]
The right subtree of the root is symmetric. It also contains the perfect part of (2^{h-1} - 1) nodes (levels (1) to (h-1) of the right half). The remaining nodes of the last level, namely [ \max\bigl(0,; (l+1) - 2^{h-1}\bigr), ] fall into the right half and therefore belong to the right subtree. Hence [ R = (2^{h-1} - 1) + \max\bigl(0,; l+1 - 2^{h-1}\bigr). ]
These are exactly the formulas stated in equation (14) (with the well‑known correction that the arguments of (\min) and (\max) involve (l+1) rather than (l); the third edition of the book contains a typographical error in the printed version of (14)). Thus equation (14) correctly gives the special subtree sizes in a heap.
This completes the proof. ∎