Discussion
Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of \(k\) is
Answer: A
The number of possible positions is 53.
In a min-heap every internal node is smaller than its children, so the maximum element cannot be an internal node: it must be a leaf. With 105 elements stored in an array indexed from 1, the internal nodes are indices 1 to \(\lfloor 105/2 \rfloor = 52\) and the leaves are 53 to 105:
\[ 105 - 52 = 53\ \text{leaves} \]
Any leaf can hold the maximum, since a leaf has no children to compare against. 52 counts the internal nodes instead, and 1 would assume the maximum has a fixed position, which is true only of the minimum (at the root).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development