We know that, max-Heap is a Complete Binary Tree $\implies$ either all internal nodes will have $2$ children or only one internal node will have $1$ child and other internal nodes will have $2$ children.
Now, can second minimum element be in an internal node with $2$ children? $\implies no$.
Since, second minimum cannot be greater than $2$ elements.
Can second minimum element be in an internal node with $1$ child? $\implies yes$.
Here, the only child will be the minimum element.
Moreover, this internal node with only $1$ child, if exists, will be the last internal node, after this node all leaves will be present.
So, we can safely say that second minimum will always be found in -
- a leaf node. OR
- an internal node having only $1$ child.
Now, an internal node with $1$ child exists only when $n$ is even.
Index of internal node with $1$ child (if exists) = $\frac{n}{2}$.
When $n$ is odd, index of $1^{st}$ leaf node = $\frac{n+1}{2}$
When $n$ is even, index of $1^{st}$ leaf node = $\frac{n}{2} + 1$
$\therefore$ First possible index where second minimum can be found -
When $n$ is even = $\frac{n}{2}$.
When $n$ is odd = $\frac{n+1}{2}$.
$\therefore$ First possible index where second minimum can be found $= \lceil \frac{n}{2} \rceil$.
$\therefore$ indices where second minimum can be found are $\lceil \frac{n}{2} \rceil, \lceil \frac{n}{2} \rceil + 1, \lceil \frac{n}{2} \rceil + 2, ..., n$.
