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


Top Users Apr 2017
  1. akash.dinkar12

    3826 Points

  2. Divya Bharti

    2796 Points

  3. Deepthi_ts

    2294 Points

  4. rude

    2142 Points

  5. Prashant.

    1900 Points

  6. Tesla!

    1888 Points

  7. Kapil

    1842 Points

  8. Debashish Deka

    1830 Points

  9. Arjun

    1810 Points

  10. Sanjay Sharma

    1712 Points

Monthly Topper: Rs. 500 gift card

22,177 questions
28,200 answers
63,649 comments
24,364 users