GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
248 views
In a binary max heap containing n numbers, the smallest element can be found in time?
asked in DS by (485 points) 3 19 37 | 248 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 Veteran (13.7k points) 16 55 115


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8962 Points

  4. srestha

    6460 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4892 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4052 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Popular Question makhdoom ghaya
Great Question makhdoom ghaya
Famous Question makhdoom ghaya
Notable Question PriDix
Popular Question ManojK
Reader Chandramani Adil
Regular qwerty007
Notable Question rishu_darkshadow
Popular Question Rishi yadav
Popular Question makhdoom ghaya
27,417 questions
35,262 answers
84,532 comments
33,497 users