The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
127 views
$(1)$ In a binary heap with $'n'$ elements with the smallest element at the root, the $7th$ smallest element can be found in time?

$A)\theta(nlogn)$            $B)\theta(n)$              $C)\theta(logn)$             $D)\theta(1)$

$(2)$ In binary max heap containing $'n'$ numbers, the smallest element can be found in time?

$A)\theta(n)$                $B)\theta(logn)$          $C)\theta(loglogn)$          $D)\theta(1)$

$(3)$ Consider the process of inserting an element into a max heap. If we perform a binary search on the path from new leaf to root, find the position of a newly inserted element, the number of comparisons performed are____________

$(4)$ We have a binary heap on $'n'$ elements and wish to insert $'n'$ more elements(not necessarily one after another) into this heap. The total time required for this is?

$A)\theta(logn)$           $B)\theta(n)$              $A)\theta(nlogn)$                      $A)\theta(n^{2})$
asked in Algorithms by Boss (29.4k points) | 127 views
0
Yes right
0
1) d

2)a

3) log log n

4) b
0
For $(1) C$
0
In 1 question

you are just finding not deleting
0

@Priyanka Agarwal 

Not find smallest(minimum), we need to find $7th$ smallest.

0
That's what i got confused earlier :)
0
To find 1 smallest it will take 1 comparison

to find 2 smallest

2 smallest is either the left child of root or right  child of root

 For 3 smallest only 3 elements are participating in competition i e left child of 2 smallest or right child of 2 smallest or looser of 2 level

 

 

in this manner by constant conparison we can find the kth smallest in O (1) time
0
we need to delete 6th min then find 7th min.
0
Yes you are right but it is taking log n time but a better way is possible which is taking constant time so go for that one

Please log in or register to answer this question.

Related questions

+5 votes
2 answers
3
asked Oct 26, 2016 in Algorithms by jenny101 Active (1.4k points) | 446 views
+2 votes
1 answer
7
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
48,756 questions
52,850 answers
183,548 comments
68,745 users