In a max-heap, how do the elements along any path behave when the path is…
2009
In a max-heap, how do the elements along any path behave when the path is traversed from a leaf to the root?
Answer: B. They are non-decreasing. — ConceptA max-heap satisfies the order invariant that every parent key is greater than or equal to each child key. Therefore, values cannot increase while…
- A.
They are non-increasing.
- B.
They are non-decreasing.
- C.
They are strictly decreasing.
- D.
They have no required order.
Attempted by 64 students.
Show answer & explanation
Correct answer: B
Concept
A max-heap satisfies the order invariant that every parent key is greater than or equal to each child key.
Therefore, values cannot increase while moving from the root toward a leaf; the same relation reverses direction when the path is traversed upward.
Application
Take a max-heap path whose values from root to leaf are 10, 7, 3.
Traversing the same path from leaf to root gives 3, 7, 10.
Each next value is greater than or equal to the previous value, so this upward sequence is non-decreasing.
Cross-check and contrast
Max-heap: root-to-leaf values are non-increasing, which is equivalent to leaf-to-root values being non-decreasing.
Min-heap: the inequalities reverse, so root-to-leaf values are non-decreasing.
Hence, for the max-heap specified here, the elements are non-decreasing when traversed from a leaf to the root.