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

Why can't we consider min heap with all elements being equal, it is not mention that they are unique.

So , can't we just compare once and find max element in one comparison as edge case?

---

In heaps- if n is odd then it will be complete binary tree i.e. 0 or 2 child so you can apply L=I+1 and all.

---

To find the total number of nodes we use 2^0 +2^1+2^2+.......+2^h =n where h is height of the tree.

so , here 2^h = n from this we get h as 9 , so n=2^9 ->512,

we know to compare 512 number , we just require 511 comparisions 

Note point given min heap so, that we will find maximum value in leaf node , it many present on any leaf node , if it is complete or perfect binary tree then we can find maximum value at right subtree ->right depth leaf  , in this case no. of comparisions = 9 (i.e h) 

correct me if i'm wrong 

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

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

---

Yes

---

@Abhrajyoti00 Little correction: That leaves formula should be floor, otherwise leaves will become 513.

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 :-)

---

Would like to add another point. Since they have not mentioned anything about the elements being distinct...
Above solution is perfect considering the case that the elements are distinct.

Suppose the elements are NOT distinct, and for e.g. there are multiple copies of the maximum element.
In this case, non-leaf elements can also contain copies of the maximum but the leaves must have at least one copy of the maximum element.

---

nice ans

Answer 3

Complete binary tree is a binary tree,so

Total no.of nodes=no.of internal nodes +no. Of leaf nodes

N=L+I

N=L+L-1=2L-1

1023=2L-1

2L=1024

L=512

No. Of comparisons to find minimum or maximum= no.of elements -1

                                                                                            =512-1=511

Answer 4

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.

 

Comments

Bro:-Non leaf elements may also contain max element but along with non leaf it will must  be at one of leaf node also.

---

That's correct 

Answer 5

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.

Answer 6

In generally ,heap is in two forms i.e one is min heap and second one in max heap;

heap always follows complete binary tree;

min heap means parent<=child

max heap means parent>=child

In this question ,they are asking about in which place max element present in min heap(which contains 1023 element);

In min heap ,max element always present in leafs(even if it contains duplicates). 

Due to that reason ,0^th -level contains 1 element

0th -level contains 1 element

1st -level contains 2elements

2^nd  -level contains 4elements

...upto 8^th level contains 2^0 +2^1+2^2+….+2^8=2^9-1(according to GP formula) which is equal to 511 elements.

remaining elements are 512 elements ,511 comparisions required to compare 512 elements(the elements which are present on the leafs)