248 views
In a binary max heap containing n numbers, the smallest element can be found in time?
asked in DS | 248 views

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 Veteran (13.7k points) 16 55 115