GATE CSE 2006 | Question: 10

Question

In a binary max heap containing $n$ numbers, the smallest element can be found in time 

• A.  $O(n)$
• B.  $O(\log n)$
• C.  $O(\log \log n)$
• D.  $O(1)$

Comments

then please explain it , the correct answer is 510 

but as per the logic in above question answer is 1021

Consider the array representation of a binary min-heap containing 1023 elements. Let p and q be the number of comparisons required to find the maximum and second minimum element in the heap, the value of p-q

is

---

A

---

it will take O(N) time , as it's MAX heap so all potential min elements will be in leaf level( last level), and number of leaf node is ceil(n/2) , so if we apply one pass of selection sort in last level it will take O(n) time only

Answer 1

• A. $O(n)$
  
  In a max heap, the smallest element is always present at a leaf node. Heap being a complete binary tree, there can be up to $\frac{n}{2}$ leaf nodes and to examine all of them we would need $O(n)$ time.

Comments

@srestha $ma'am$ can you please guide me why is it or how is it taking $O(n)$ time.

As I was thinking that we already have a MAX heap with us, now we can make use of MIN-heapify to get MIN heap

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest != i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

---

Heap is complete or almost complete binary tree. It will never be skewed....

---

heap is already there just perform hepify at (n-1)/2th node  to root
no need to reconstruct the heap

 this approach by asu , I don't think is correct .

First why we will do heapify at (n-1)/2 th node only ? it does not make sense. as the smallest node can by any one of the leaves as leaves are almost n/2 by definition. 

So to convert Max heap to Min Heap first of all we need to go to every non leaf node which are from 1 to n/2 and perform min-heapify on them that will take in total O(nlogn) . so this approach is not good . Better way is to get all the leaves and then perform the searching for smallest node. that will take O(n) bcz we know leaves are from floor(n/2)+1 to last . 

Answer 2

The smallest element in a max heap would always be in the last level. => Search all leafs.

No. of leafs = No. of internal nodes + 1.

In an asymptotic sense, we can say No. of leafs = No. of internal nodes. If total nodes = n, leafs = $O(\frac{n}{2})$ = Internal nodes.

And, $O(\frac{n}{2}) = O(n)$

So, Option A.

Answer 3

Convert the heap into array and do linear search that comes O(n).

Comments

If you are converting heap into array then why to do Linear search?

---

there is no need of linear search,we know the leaf in a heap will be present at floor(n/2+1) to n. just put the heap into array and directly search the array from that position. in worst case it will be o(n/2)=o(n)

Answer 4

🔍 Where’s the Smallest Element?

• In a complete binary tree (which a heap is), at least half the nodes are leaves.

• So the smallest element is guaranteed to be among the last ⌊n/2⌋ nodes.

• You have no ordering among leaves, so you must scan them all.

✅ Correct Answer: A. O(n)

• You need to check all leaves to find the smallest.

• That’s Θ(n) in the worst case, because you might have to inspect every leaf.

Answer 5

In a max heap, minimum value will be at the leaf nodes. Hence we will have to run a for loop from n/2 to n and check sequentially.

The time complexity of one for loop from n/2 to n will be O(n).

Hence option A. 

Answer 6

In n element max heap, smallest element is one of the leaf.. in array representation of max heap, leaves index start from floor(n/2)+1 to n. And there will be max n/2 elements present at last level (height 0).

 

Just do a for loop from floor(n/2)+1 to n

In which keep track of smallest element

There will be O((n/2)-1) = O(n) comparisons ( we need only 1 element to find)..

Answer =A