GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
175 views
In a binary max heap containing n numbers, the smallest element can be found in time?
asked in DS by (427 points)   | 175 views

1 Answer

+5 votes

We have two ways to find the smallest element from $n$  number Max Heap

Way 1st


$\Rightarrow$ Construct(Build) a Minheap from the given Maxheap which will take $\Rightarrow \Theta \left ( n \right )$ $\Rightarrow$ 1st element of the array(heap) will be minimum ,it will take $\Theta \left ( c \right )$.$\Rightarrow T\left ( n \right )= \Theta \left ( n \right )+\Theta \left ( c \right )\approx \Theta \left ( n \right )$


Way 2nd-:Using MaxHeap Only.$\Rightarrow$In MaxHeap ,smallest element are present in the last level 'L' or 2nd last level 'L-1',where L is the level of our graph(In simple words Smallest element will present in the Leaves of our heap/graph).How to find Leaves?

$\Rightarrow$ Leaves will be from $\left \lfloor n/2 \right \rfloor+1$ to $n$ $\Rightarrow$ search the smallest element among these numbers which will also take $\Theta \left ( n \right )$.

 

answered by Boss (8.4k points)  


Top Users Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1491 Points

  5. Debashish Deka

    1450 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1278 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1228 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    410 Points

  2. akankshadewangan24

    334 Points

  3. Arjun

    268 Points

  4. Abhisek Das

    230 Points

  5. Bikram

    208 Points


23,433 questions
30,147 answers
67,595 comments
28,476 users