GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
128 views
In a binary max heap containing n numbers, the smallest element can be found in time?
asked in DS by (417 points)   | 128 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.1k points)  


Top Users Mar 2017
  1. rude

    4758 Points

  2. sh!va

    3014 Points

  3. Rahul Jain25

    2830 Points

  4. Kapil

    2636 Points

  5. Debashish Deka

    2442 Points

  6. 2018

    1514 Points

  7. Vignesh Sekar

    1416 Points

  8. Akriti sood

    1298 Points

  9. Bikram

    1286 Points

  10. Sanjay Sharma

    1076 Points

Monthly Topper: Rs. 500 gift card

21,471 questions
26,802 answers
61,041 comments
23,037 users