Question 57

Properties of a binary min-heap:

• In a min-heap, every parent node has a key less than or equal to the keys of its children: $\text{heap}[p] \le \text{heap}[2p]$ and $\text{heap}[p] \le \text{heap}[2p + 1]$.
• As a consequence, no internal node can hold the maximum key in the heap, because each internal node has at least one child with a key $\ge$ itself.
• Therefore, the maximum element must reside in one of the leaf nodes.

Count the leaf nodes:

• For an array-based complete binary tree of size $N = 1023$:
  • Number of internal nodes = $\lfloor N / 2 \rfloor = \lfloor 1023 / 2 \rfloor = 511$ (indices 1 through 511 in 1-based indexing).
  • Number of leaf nodes = $N - \lfloor N / 2 \rfloor = 1023 - 511 = 512$ (indices 512 through 1023).

Finding the maximum among the leaves:

• The min-heap property enforces no ordering relationship among the leaf nodes.
• To find the maximum among $L = 512$ completely unordered elements, any comparison-based algorithm must perform at least $L - 1$ comparisons in the worst case:
  $$\text{Comparisons} = 512 - 1 = 511$$