Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
The smallest element in a max-heap must be at a leaf node. To see why, let’s think about what would happen if the smallest element were at an internal node (a node with at least one child).
In a max-heap, the max-heap property requires that every parent is greater than or equal to its children:
\[A[\textsc{Parent}(i)] \ge A[i]\]If the smallest element were at an internal node, then that node would have at least one child. But the max-heap property says the parent must be at least as large as its children. This means the children would have to be less than or equal to the smallest element. Since we assumed the smallest element is already the minimum of all elements in the heap, there cannot be any element smaller than it. Therefore, this situation is impossible (given that all elements are distinct).
The only nodes that don’t have this constraint are the leaves, because they have no children. The smallest element can be at any leaf without violating the max-heap property.