GATE CSE 2020 | Question: 47

Question

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

Comments

binary min-heap containing 1023 elements

One of the leaf nodes contains the maximum element.

(ceil(n/2) – 1) is ceil(1023/2) = 512 ; 512-1 = 511

---

I HAVE A DOUBT

Here if we had to find maximum comparison then what would be answer here?

isisnt here minimum and maximum comparison will be same?

---

To find no of levels

$(2ka$ $power(n+1)/(2-1))$ = $1023$

so $ n+1 = 10$

n=9 = if level start from 0

Answer 1

If a heap has $1023$ elements, it'll contain $512$ leaves and since it is a MIN-HEAP, the maximum will be present in the leaves. (Why? Assume it is not, then there will be some elements present under it and this will violate the min-heap property.)

We can visualise it this way. At each level starting with root level, number of elements are

$1-2-4-8-16-32-64-128-256-512$ (this is the last level, hence leaves)

So if we have $n$ elements in an array, we know that to find the maximum it takes $n-1$ comparisons.

In this case, $n = 512$, so the answer should be $511$.

Some other excellent questions on finding maximum-minimum:

• https://gateoverflow.in/1917/gate2014-1-39
• https://gateoverflow.in/27198/tifr2014-b-10
• https://gateoverflow.in/27194/tifr2014-b-9

Comments

To find the maximum element among ‘n’ elements is it (n-1) comparisons or [(n/2)-1] as given in GATE CSE 2014 Set 1 | Question: 39 - GATE Overflow? Also how many comparisons required to find the minimum element?

Edit: Got it. To find the maximum OR minimum -> $n-1$ min. comparisons reqd.

To find the minimum AND maximum -> $\lceil3n/2-2\rceil$ min. comparisons required.

In this q, leaves are from $\lceil n/2\rceil+1 \ to \ n$, thus in total $512$ elements in leaves. Hence we require $511$ comparisons in minimum.

---

How are we calculating the leaf nodes? Just by counting them in the power of 2 for each level?

---

Yes

Answer 2

Answer : 511

In Binary min-heap , Maximum element will be present in the leaf nodes .

so, we already know that from "floor(n/2)+1 to n" leaf nodes are present

floor(1023/2)+1 to 1023 = 512 to 1023 => total 512 elements (put these all in an array i:e,[all the elements in array are unsorted] ) .

 

now we know that to find maximum in an array we will surely require minimum n-1 comparisons(you can apply any searching algorithm , n-1 comparison must be needed) .

so, 512-1 = 511 

Comments

Thanks :-)

Answer 3

Minimum 511 comparisons  required.

A heap with n nodes satisfies a property that it has (1 to floor(n/2)) non leaf elements & (floor(n/2)+1 to n) leaf elements.

So, the non leaf node cannot contain the maximum element. To look for max element we have to search the leaves.

applying the above formulae, we'll get 512 leaves.

as we know for m elements, minimum m-1 comparison is required to find min/max element. 

so we need minimum of 512-1=511 comparisons to find the max element of heap.

 

Answer 4

In a binary min-heap the maximum element will always remain in the leaf node

Let us consider that all the elements in the heap is stored in an array of n+1 elements starting from index 1.(We are keeping index 0 free for easier and minimal calculations, it can be done with index 0 also)

For a given node arr[i],

the left child will be – arr[2*i]

the right child will be – arr[2*i + 1]

 

The leaf nodes cannot have any child, so the value of 2*i will always exceed n, that means any leaf node will come after any non leaf node in the array representation, so we have to traverse the last floor(n/2) + 1 elements to get the maximum element.

Total number of leaves = 511 + 1 = 512

To find the maximum of 512 elements we have to do atleast 511 comparisons.