Question

Suppose H is a binary min-heap with n nodes, Prove the following facts:

Any algorithm that must nd the maximum key of the heap must search all of the leaf nodes.

Answer 1

Answer: If we go by the Brute Force Approach We can check all the nodes in the min heap to get the maximum element. Note that this approach works on any binary tree and does not makes use of any property of the min heap. It has a time and space complexity of O(n). Since min heap is a complete binary tree, we generally use arrays to store them, so we can check all the nodes by simply traversing the array. If the heap is stored using pointers, then we can use recursion to check all the nodes.

Alternatively the min heap property requires that the parent node be lesser than its child node(s). Due to this, we can conclude that a non-leaf node cannot be the maximum element as its child node has a higher value. So we can narrow down our search space to only leaf nodes. In a min heap having n elements, there are ceil(n/2) leaf nodes. The time and space complexity remains O(n) as a constant factor of 1/2 does not affect the asymptotic complexity.

Hence any algorithm that must nd the maximum key of the heap must search all of the leaf nodes.