Question

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

The maximum key is at one of the leaves.

Answer 1

The min-heap has the following 2 properties:

1. It is a complete binary tree, which means all the levels in min heap are filled, except maybe the last one. It may be filled or not.

2. The value of all the parent nodes must always be less than or equal to the children.

Now, let us suppose that in a min heap the maximum key is not a leaf node but any random node in middle. This node will have 2 children as defined by the first property (the heap is complete binary tree). Being in a min heap, both its children should be greater than itself. But then it won't be the maximum key because if children are smaller, it would violate the second property. As our assumption is wrong, therefore we can conclude that the maximum node will always be one of the leaves.