Show the following regarding the maximum item in the heap a

Show the following regarding the maximum item in the heap:

a. It must be at one of the leaves.

b. There are exactly [N / 2 ] leaves

c. Every leaf must be examined to find it.

Solution

Finding max element in min heap:-

a) every internal node(including root) in min heap is less than all its childrens(childs,grandchilds,grandgrand childs..), so internal node should not be a maximum, because there is a child which is greater than the parent, Hence , the maximum element must be at one of the leaves.

b)Heap has a property, that is, it is left justified (leftiest) and complete tree, while inserting nodes, we have to insert from left to right, and fill leftmost vacancy parent completely, before moving to next parent, means you to assign the childs from left to right, if one parent has two childs(completely filled) then move to immediate right parent and fill it,, because of this property the heap has exactly [N/2] leaves..

c)so , we know that maximum element is one of the leaves, it may be any leaf node, we can\'t skip any leaf node, because there is no pattern, hence we have to search every leaf to find the maximum element..