1. **Problem Statement:** We have a complete binary tree $T$ of size $n$ where the last level is fully filled from left to right. 2. **Part (a): Number of nodes at height $h$** - The height of leaves is 0. - The height of a node corresponds to the distance (in edges) to the deepest leaf in its subtree. - In a complete binary tree, the number of nodes at height $h$ is the number of nodes at level $\text{max_height} - h$. - The height of the root is $\lfloor \log_2 n \rfloor$. - At level $l$, there are at most $2^l$ nodes. - Therefore, the number of nodes at height $h$ is: $$\text{nodes}(h) = \min\left(2^{\lfloor \log_2 n \rfloor - h}, \max\Big(0, n - (2^{\lfloor \log_2 n \rfloor + 1} - 1) + 2^{\lfloor \log_2 n \rfloor - h}\Big)\right)$$ Simplified when all nodes exist except possibly the last level: $$\text{nodes}(h) = 2^{\lfloor \log_2 n \rfloor - h}$$ for $0 \leq h \leq \lfloor \log_2 n \rfloor$. 3. **Part (b): Bubble-Down complexity for one node at height $h$** - Bubble-Down (or sift-down) operation in heap is proportional to height $h$, as it may move down to leaves. - Thus, time complexity for one node at height $h$ is: $$O(h)$$ 4. **Total time complexity to Bubble-Down all nodes at height $h$ during Heapify:** - Number of nodes at height $h$ is $2^{\lfloor \log_2 n \rfloor - h}$. - Each Bubble-Down costs $O(h)$. - So total time at height $h$ is: $$O(h \cdot 2^{\lfloor \log_2 n \rfloor - h}) = O\left(h \cdot \frac{n}{2^{h+1}}\right)$$ 5. **Justification:** - Heapify runs Bubble-Down on all nodes from bottom up. - Summing over all heights $h$, the total complexity is: $$\sum_{h=0}^{\lfloor \log_2 n \rfloor} O\left(h \cdot \frac{n}{2^h}\right) = O(n)$$ - This shows Heapify can be done in linear time $O(n)$, faster than the naive $O(n \log n)$. **Final answers:** - Number of nodes at height $h$: $\boxed{2^{\lfloor \log_2 n \rfloor - h}}$ - Bubble-Down time per node of height $h$: $\boxed{O(h)}$ - Total Bubble-Down time for all nodes at height $h$: $\boxed{O\left(h \cdot \frac{n}{2^h}\right)}$