GATE Computer Science (CS) 2020 Solved Papers

Question : 51 of 65

Marks: +1, -0

Consider the array representation of a binary min-heap containing 1023 element. The minimum number of comparisons required to find the maximum in the heap is ______.

Your Answer:

Validate

Solution:

Min-heap contains 1023 elements.
Min-heap means, parent should be minimum or equal to it's children so, max children could be either left or right one.
Following this logic, maximum can be definitely at leaf nodes.

No. of elements in leaf

=[\;{n}/{2}]=[\;{1023}/{2}]=512

To find maximum among 512 elements, no. of comparisons needed is 511 .

Go to Question:

Prev Question

Next Question