GATE CS 2020 Q47 — Binary Heaps

In a binary min-heap, the parent node is always smaller than or equal to its children. Consequently, the maximum element cannot be an internal node (as any internal node is smaller than its descendants). Thus, the maximum element must reside in one of the leaf nodes.

For a binary heap represented as an array of size $N$ (using 1-based indexing):

• The internal nodes are located at indices $1$ to $\lfloor N/2 \rfloor$.
• The leaf nodes are located at indices from $\lfloor N/2 \rfloor + 1$ to $N$.

Given $N = 1023$:

Thus, the leaf nodes are located at indices from $512$ to $1023$.

The total number of leaf nodes ($L$) is:

Since there is no ordering guarantee among the leaf nodes, finding the maximum element among these $L$ elements requires finding the maximum of an unsorted list of size $L$.

The minimum number of comparisons required to find the maximum of $L$ unsorted elements is: